借鉴:DeepinC
逐层递推：设$dp[i][j]$表示到了第i层，这层用了某$j$种颜色的总方案数。

注意这里为了方便去重，所以dp的含义里是已经确定了j种颜色，所以不要乘上 $C_{m}^j$
那么再设$s[i]$是填到第i曾为止的总方案数那么$s[i]$=$\sum dp[i][j]*C[m][j]$

还需要预处理一下$g$数组，$g[i][j]$表示用恰好$i$种颜色填满$j$个格子的方案数。而这$j$种颜色也是未钦定的所以不带组合数。

那么$dp$的转移式也就有了，$dp[i][j]=(s[i-1]-dp[i-1][j])*g[j][a[i]]$;

只从上一层转移而来所以可以滚动。

$f$的预处理也很简单，转移就是从长度短$1$的状态中选择一种颜色填上。

$g[i][j]=g[i-1][j]*(j-1)+g[i-1][j-1]*j$;即如果不新增颜色的话那么你能从已有的$j$种里除上一位刚填的那一种外其他的颜色里选一种，即j-1。

如果你新开了一种颜色，那么就要决定这新开的一种颜色是现有的$j$种里的哪一种，即乘$j$。

然后想一想简化：当模数不是质数时除法会出问题而加减乘都没事。然而整个代码里只有组合数那一步需要除法。

那么怎么搞掉组合数呢？

$s[i]=\sum dp[i][j]*C[m][j]$，想办法压掉$C[m][j]$。

$dp[i][j]=(s[i-1]-dp[i-1][j])*g[j][a[i]]*C[m][j]=s[i-1]*g[j][a[i]]*C[m][j]-dp[i-1][j]*g[j][a[i]]$

注意,其实这里有点问题，也就是$dp[i][j]$只用乘一次$C[m][j]$，就令$dp[i-1][j]$中含有一个$C[m][j]$即可。

因此$dp[i][j]=s[i-1]*g[j][a[i]]*C[m][j]-dp[i-1][j]*g[j][a[i]]$

需要一些脑洞，我们新开一个数组

$f[i][j]=f[i-1][j-1]*(m+1-j)+f[i-1][j]*(j-1)$

恰好替代了

$g[j][a[i]]*C[m][j]$。

#include<cstdio>
#define ll long long
int n,p,m,a[1000005],f[5005][5005],dp[5005],g[5005][5005],ld;
main(){
    freopen("kalanchoe.in","r",stdin);
    freopen("kalanchoe.out","w",stdout);
    scanf("%d%d%d",&n,&m,&p);
    for(int i=1;i<=n;++i)scanf("%d",&a[i]);
    f[0][0]=ld=g[0][0]=1;
    for(int i=1;i<=5000;++i) 
        for(int j=i;j<=5000;++j)
               f[i][j]=((ll)f[i][j-1]*(i-1)+(ll)f[i-1][j-1]*(m+1-i))%p,
            g[i][j]=((ll)g[i][j-1]*(i-1)+(ll)g[i-1][j-1]*i)%p;
    for(int i=1;i<=n;++i,ld=dp[0],dp[0]=0) 
        for(int j=1;j<=a[i]&&j<=m;++j)
            (dp[0]+=(dp[j]=((ll)ld*f[j][a[i]]-(j<=a[i-1])*(ll)dp[j]*g[j][a[i]])%p))%=p;
    printf("%d\n",((ll)ld+p)%p);
}
//s[i]=Σdp[i][j]*C[m][j];