首先，我们考虑枚举所有的 \(a_i\) 的和 \(sum\)。如果 \(y\) 可以满足条件，那么 \(y\equiv sum-y(\bmod k)\)，也就是 \(2y\equiv sum(\bmod k)\)
然后考虑有多少种可能的答案。我们发现，当 \(k\) 是奇数的时候，\(y\) 有唯一解。当 \(k\) 是偶数的时候，\(y\) 有两个解 \(y_1\) 和 \(y_2=y_1+k/2\) 或者无解。
那么我们先考虑 \(y\) 有唯一解的情况。我们考虑容斥，设 \(r_i\) 表示至少有 \(i\) 个位置是 \(y\) 的方案数。
考虑如何计算 \(r_i\)，首先枚举哪些位置，是 \({n\choose i}\)，然后剩下的所有位置都是用 \([0,k-1]\) 填，用这些数造任意的数，就是前面的随便填，最后一个补上，所以 \(r_i={n\choose i}k^{n-i-1}\)，但是 \(r_n\) 比较特殊。当且仅当只用 \(y\) 能达成 \(sum\)，\(r_n=1\)
然后就可以容斥，\(ans=\sum_{i=0}^n(-1)^ir_i=\sum_{i=0}^{n-1}(-1)^ir_i+(-1)^n res\)
展开 \(r_i\)，\(\sum_{i=0}^{n-1}(-1)^ir_i=\sum_{i=0}^{n-1}(-1)^i{n\choose i}k^{n-i-1}\)，提出一个 \(k^{-1}\)，补上 \(i=n\) 项，得到 \(\dfrac{1}{k}(\sum_{i=0}^n{n\choose i}(-1)^ik^{n-i}-(-1)^n)\)
我们发现前面被凑成了二项式定理的形式，就可以直接转化成 \(\dfrac{1}{k}((k-1)^n-(-1)^n)\)
接下来考虑 \(k\) 是偶数。如果 \(y\) 无解，显然随便计算。如果 \(y\) 有两个解，那么 \(r_i\) 还要乘上 \(2^i\)，这样推出来就是 \(\dfrac{1}{k}((k-2)^n-(-2)^n)\)。然后考虑如何计算 \(r_n\)。我们发现，如果我们可以把解写成 \(xy_1+yy_2\equiv sum(\bmod k)\)，那么我们就可以把 \(y_2\) 拆出来，变成 \((x+y)y_1+y(k/2)\equiv sum(\bmod k)\)。而 \(y\) 这样就等价于 \(y\bmod 2\)，那么我们只需要直接检测一下 \(y=0/1\) 即可。然后我们可以在前面随便填，一共 \(2^{n-1}\) 种，最后一位由前面的决定即可。
ll n,k,P;
inline ll fpow(ll a,ll p){
if(!p)return 1;
ll res=fpow(a,p>>1);
if(p&1)return res*res%P*a%P;
return res*res%P;
}
inline ll inv(ll a){
return fpow(a,P-2);
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>k>>P;
ll ans=0;
if(k&1){
rd(i,k){
int y=0;
rd(j,k)if(2*j%k==i)y=j;
ll res=(fpow(k-1,n)-fpow(P-1,n)+P)%P*inv(k)%P;
ans=(ans+res)%P;
if(n%k*y%k==i)ans=(ans+fpow(P-1,n))%P;
}
}else{
rd(i,k){
int x=-1;
rd(j,k)if(2*j%k==i){
x=j;break;
}
if(x==-1){
ll res=fpow(k,n-1);
ans=(ans+res)%P;
}else{
ll res=(fpow(k-2,n)-fpow(P-2,n)+P)%P*inv(k)%P;
ans=(ans+res)%P;
if(n%k*x%k==i||(n%k*x%k+k/2)%k==i){
ans=(ans+fpow(2,n-1)*fpow(P-1,n)%P)%P;
}
}
}
}
ans=(fpow(k,n)-ans+P)%P;
cout<<ans%P<<endl;
return 0;
}
//Crayan_r