题解：

容斥（？）+$dp$。

定义状态$dp[i][j]$表示前$i$层，其中第$i$层用了$j$种颜色。

这个时候我们发现还缺一个系数，就是用$i$种颜色涂$j$个格子的方案数（颜色无顺序要求）。

定义这个东西叫$f[i][j]$。

然后有：$$dp[i][j]=f[l[i]][j]*(C^{m}_{j}*\sum dp[i-1][k]-dp[i-1][j])$$

结果发现这个东西涉及到组合数取模非质数。

当场自闭。

后来看题解，发现这个东西有个巧妙的处理方法。

把$f$的定义改一下，要求涂色时颜色有序，比如$12345$、$12123$合法，而$54321$、$12356$不合法。

于是我们发现$f$是可以递推的。$f[i][j]=f[i-1][j-1]+(j-1)*f[i-1][j]$

然后代码：

#include
     
      #include
      
       #include
       
        using namespace std;typedef long long ll;const int L = 5050;const int N = 1000050;template
        
         inline void read(T&x){    T f = 1,c = 0;char ch=getchar();    while(ch<'0'||ch>'9'){
   if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){c=c*10+ch-'0';ch=getchar();}    x = f*c;}int n,m,p,l[N],op,mx;ll A[L],B[L],dp[2][N],f[L][L];void init(){    A[0]=1;    for(int i=1;i<=mx;i++)A[i]=A[i-1]*(m-i+1)%p;    B[0]=1;    for(int i=1;i<=mx;i++)B[i]=B[i-1]*i%p;    f[0][0]=1;    for(int i=1;i<=mx;i++)        for(int j=1;j<=i&&j<=m;j++)            f[i][j]=(f[i-1][j-1]+((j-1)*f[i-1][j]%p))%p;}int main(){    read(n),read(m),read(p);    for(int i=1;i<=n;i++)read(l[i]),mx=mx>l[i]?mx:l[i];    init();    for(int i=1;i<=n;i++,op^=1)    {        ll k=0;        if(i==1)k=1;        else for(int j=1;j<=m&&j<=l[i-1];j++)k=(k+dp[op][j])%p;        for(int j=1;j<=m&&j<=l[i];j++)            dp[!op][j]=f[l[i]][j]*((A[j]*k%p-B[j]*dp[op][j]%p+p)%p)%p;        for(int j=1;j<=m&&j<=l[i-1];j++)            dp[op][j]=0;    }    ll ans = 0;    for(int i=1;i<=m&&i<=l[n];i++)ans=(ans+dp[op][i])%p;    printf("%lld\n",ans);    return 0;}