显然颜色数量不会超过\(lim=\min(m,n/S)\)

考虑容斥，计算恰好出现了\(S\)次的颜色有至少\(i\)种的方案数\(f[i]\)，钦定\(i\)种颜色正好放\(S\)种

有\(m\)种颜色选\(i\)种，所以乘一个\(C_m^i\)

然后这n个位置分成\(i+1\)个部分：被钦定的\(i\)种颜色，每个有\(S\)个；剩下的\(m-i\)种颜色，一共\(n-iS\)个。先看作是可重的全排列数，那么方案就有\(\frac{n!}{(S!)^i(n-iS)!}\)种。前\(i\)各部分都是只有一种颜色，后面部分每个有\(m-i\)种取法，所以还有一个\((m-i)^{n-iS}\)

综上，\(f[i]=C_m^i\cdot \frac{n!}{(S!)^i(n-iS)!}\cdot(m-i)^{n-iS}\)

接下来就是答案，恰好出现了\(S\)次的颜色有正好\(i\)种的方案数\(ans[i]\)

用容斥，\(ans[i]=\sum_{j=i}^{lim}(-1)^{j-i}C_j^if[j]\)

那个组合数很麻烦，拆开

\(ans[i]=\sum_{j=i}^{lim}(-1)^{j-i}\frac{j!}{i!(j-i)!}f[j]\)

\(ans[i]\cdot i!=\sum_{j=i}^{lim}\frac{(-1)^{j-i}}{(j-i)!}f[j]\cdot j!\)

这就可以直接用NTT做了，如果不知道怎么做的可以先写zjoi2014 力

#include
    
     #define il inline#define vd void#define mod 1004535809typedef long long ll;il int gi(){    int x=0,f=1;    char ch=getchar();    while(!isdigit(ch)){        if(ch=='-')f=-1;        ch=getchar();    }    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();    return x*f;}il int pow(int x,int y){    int ret=1;    while(y){        if(y&1)ret=1ll*ret*x%mod;        x=1ll*x*x%mod;y>>=1;    }    return ret;}#define inv(a) pow((a),mod-2)const int G=3,iG=inv(G);int fact[10000001],W[100010];int A[262147],B[262147],rev[262147];il int C(int n,int m){    if(n
     
      i)std::swap(A[rev[i]],A[i]);    for(int o=1;o
      
       <<=1){        int W=pow(t?G:iG,(mod-1)/(o<<1));        for(int*p=A;p!=A+n;p+=o<<1)            for(int i=0,w=1;i
       
        >1]>>1)|((i&1)<