计数
我们可以发现直径上的才会和其他点构成直角
我们处理出有多少条直径
随即思考如何计数
定义 d 为 直径对数 n，m 点数 颜色数 sy 除直径外剩余点
要是直径上的不同 ： m(m-1) ^ d 选出不同颜色对个数 * 其他点任意颜色 m^sy
要是直径上颜色相同 那么这个颜色只能是这两个点
我们枚举有多少个直径颜色相同即可
如果有i个
C(d,i)C(m,i)A(i,i) 然后剩余点选的颜色就要少i (m-i)(m-i-1)^(d-i) 其他点颜色 (m-i)^sy
乘起来即可
我们注意一直乘法不会变号 所以直接对res》=0 才加上即可
int a[N],b[N];
int qmi(int a, int k,int p) {
int res = 1;
while (k) {
if (k & 1) res = res * a % p;
a = a * a % p;
k >>= 1;
}
return res;
}
int inv(int x){return qmi(x,mod-2,mod);}
int C(int x, int y) {
if (x < 0 || y < 0 || x < y) return 0;
return a[x] * b[y] % mod * b[x-y] % mod;
}
void init() {
a[0] = b[0] = 1;
for (int i = 1; i < N; i ++ )a[i] = a[i - 1] * i % mod;
b[N - 1] = qmi(a[N - 1], mod - 2 , mod);
for (int i = N - 2; i >= 0; i -- )b[i] = b[i + 1] * (i + 1) % mod;
}
void solve(){
init();
int n,m;cin>>n>>m;
vector<int>a(n+1),s(n+1);
int sum=0,d=0;
map<int,int>v;
for(int i=1;i<=n;i++){
cin>>a[i];
s[i]=a[i]+s[i-1];
v[s[i]]++;
sum+=a[i];
}
for(int i=0;i<=n;i++){
if(s[i]<sum/2&&v[s[i]+sum/2]){
d++;
}
}
if(n==1){
cout<<m<<endl;
return;
}
if(sum%2)d=0;
vector<int>A(d+1);
for(int i=1;i<=d;i++){
if(i==1)A[i]=1;
else A[i]=A[i-1]*i%mod;
}
int sy=n-d*2;
int ans=qmi(m,sy,mod)*qmi(m*(m-1)%mod,d,mod)%mod;
for(int i=1;i<=d;i++){
int res=qmi(m-i,sy,mod)*qmi((m-i)*(m-i-1)%mod,d-i,mod)%mod*C(m,i)%mod*C(d,i)%mod*A[i]%mod;
if(res>=0)(ans+=res)%=mod;
}
cout<<ans<<endl;
}