解题报告

先来介绍一波原根：如果 $\forall i\not=j,g^i\not\equiv g^j\ (mod\ P)$ ，那么 $g$ 是 $P$ 的一个原根，如果 $P$ 是素数那么一定有原根。

原根有什么用呢？如果有了原根，那么我们就可以做到模意义下取对数，也就是说我们我可以把模意义下乘法变成模意义下加法，这是很重要的一个作用。

怎么求原根？爆枚！一般原根都不会很大，所以直接爆枚，判断的时候可以这样：对于 $P-1$ 的所有素因子 $p$ ，如果均满足 $a^{P-1\over p_i}\not=1$ 那么说明 $a$ 是 $P$ 的一个原根。证明我不会……

这道题很明显可以矩乘优化DP，但是复杂度是 $O(P^3log_2m)$ ，直接炸飞。这时候就需要用到原根的套路，用原根把转移矩阵中的乘法换成加法，那么就会发生一件很奇妙的事情：转移矩阵是循环的，也就是说只需要知道第一列就可以推知整个矩阵，这时候矩乘可以做到 $O(P^2)$ ，就可以过了。

会发现矩乘是个循环卷积的形式，甚至可以用循环卷积FFT做到更优秀的复杂度，不过我不会……

示例程序

#include<cstdio>
using namespace std;
typedef long long LL;
const int maxp=1000,MOD=1e9+7;

int n,m,P,g,pw[maxp+5],Lg[maxp+5],p[maxp+5],D[maxp+5];bool pri[maxp+5];
int S[maxp+5],T[maxp+5],c[maxp+5],ans;

inline void Make(){
    for (int i=2;i<=maxp;i++){
        if (!pri[i]) p[++p[0]]=i;
        for (int j=1,t;j<=p[0]&&(t=i*p[j])<=maxp;j++)
            if (i%p[j]) pri[t]=true; else {pri[t]=true;break;}
    }for (int i=1;i<=p[0];i++) if (!((P-1)%p[i])) D[++D[0]]=(P-1)/p[i];
}
inline int Pow(int w,int b,int MOD) {int s=1;for (;b;b>>=1,w=(LL)w*w%MOD) if (b&1) s=(LL)s*w%MOD;return s;}
inline bool check(int g) {for (int i=1;i<=D[0];i++) if (Pow(g,D[i],P)==1) return false;return true;}
inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;}
inline void Mul(int *a,int *b,int P){
    for (int i=0;i<P;i++)
        {c[i]=0;for (int j=0;j<P;j++) AMOD(c[i],(LL)a[j]*b[(i-j+P)%P]%MOD);}
    for (int i=0;i<P;i++) a[i]=c[i];
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%d%d",&n,&m,&P);Make();for (g=2;g<=MOD-1;g++) if (check(g)) break;
    for (int i=0,w=1;i<P-1;i++,w=w*g%P) pw[i]=w,Lg[w]=i;
    for (int i=1,x;i<=n;i++) scanf("%d",&x),T[Lg[x]]++;
    S[0]=1;for (int b=m;b;b>>=1,Mul(T,T,P-1)) if (b&1) Mul(S,T,P-1);
    for (int i=0;i<P-1;i++) AMOD(ans,(LL)S[i]*pw[i]%MOD);
    ans=(LL)ans*Pow(Pow(n,m,MOD),MOD-2,MOD)%MOD;printf("%d\n",ans);return 0;
}