令$f[k]$为钦定$k$种颜色恰好出现$S$次的方案数
$$ f[k]=\binom{m}{k}\frac{n!}{(S!)^i(n-kS)!}(m-k)^{n-kS} $$

套二项式反演
$$ g[k]=\sum_{i=k}^{\min(\lfloor n/S \rfloor)} (-1)^{i-k}\binom{i}{k}f[i] $$

化卷积

$$ \begin{aligned} g[k] &= \sum_{i=k}^{\min(\lfloor n/S \rfloor)} (-1)^{i-k}\binom{i}{k}f[i] \\\ &=\sum_{i}(-1)^{i-k}\frac{i!}{k!(i-k)!}f[i]\\\ &=\frac{1}{k!}\sum_{i}(-1)^{i-k}\frac{1}{(i-k)!}\times i!f[i] \end{aligned} $$

令$A[i]=i!f[i],B[i]=(-1)^i\frac{1}{i!}$

$$ g[k]=\frac{1}{k!}\sum_{i=k}^{\min(\lfloor n/S \rfloor)}A[i]B[i-k] $$
令$t=\min(\lfloor n/S \rfloor)$

替换求和指标
$$ g[k]=\frac{1}{k!}\sum_{k\le i\le t}A[i]B[i-k]=\frac{1}{k!}\sum_{0\le i\le t-k}A[i+k]B[i] $$

令$A’[k]=A[t-k]$

$$ g[k]=\frac{1}{k!}\sum_{0\le i\le t-k}A[i+k]B[i]=\frac{1}{k!}\sum_{0\le i\le t-k}A’[t-i-k]B[i] $$

直接$\text{NTT}$计算差卷积即可。

#include <iostream>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>

namespace poly{
    #define int long long
    const int N = 4.2e6,mod = 1004535809,G = 3,Gi = 332748118;
    int rev[N],c[N];
    inline void change(int f[],int len){
        for (int i = 0; i < len; i++){
            rev[i] = rev[i >> 1] >> 1;
            if (i & 1) rev[i] |= len >> 1;
        }
        for (int i = 0; i < len; i++)
            if (i < rev[i]) std::swap(f[i],f[rev[i]]);
    }
    inline int ffpow(int a,int b){
        int res = 1;
        for (;b;b >>= 1){
            if (b & 1) res = 1ll * res * a % mod;
            a = 1ll * a * a % mod;
        }
        return res;
    }
    inline void NTT(int f[],int len,int op){
        change(f,len);
        for (int mid = 1; mid < len; mid <<= 1){
            int wn = ffpow(G,(mod - 1) / (mid << 1));
            if (op == -1) wn = ffpow(wn,mod - 2);
            for (int j = 0; j < len; j += (mid << 1)){
                int cur = 1;
                for (int k = 0; k < mid; k++){
                    int u = f[j + k];
                    int t = cur * f[j + k + mid] % mod;
                    f[j + k] = (u + t) % mod;
                    f[j + k + mid] = (u - t + mod) % mod;
                    cur = (cur * wn) % mod;
                }
            }
        }
        int inv = ffpow(len,mod - 2);
        if (op == -1)
            for (int i = 0; i < len; i++)
                f[i] = (f[i] * inv) % mod;
    }
    inline std::vector<int> mul(int a[],int b[],int n,int m){
        std::vector<int> res;
        int limit = 1;while (limit < n + m + 1) limit <<= 1;
        NTT(a,limit,1);NTT(b,limit,1);
        for (int i = 0; i < limit; i++) c[i] = a[i] * b[i] % mod;
        NTT(c,limit,-1);
        for (int i = 0; i <= n + m; i++)
            res.push_back(c[i]);
        return res;
    }
}
namespace wxy{
    #define int long long
    const int N = 4.2e6,mod = 1004535809;
    int n,m,s,fac[10000005],invfac[10000005];
    int a[N],b[N],f[N],d[N],w[N];
    std::vector<int> c;
    inline int C(int n,int m){return n<m?0:(long long)fac[n]*invfac[m]%mod*invfac[n-m]%mod;}
    inline void init(){
        fac[0]=invfac[0]=invfac[1]=1;
        for(int i=1;i<=10000000;i++)fac[i]=(long long)fac[i-1]*i%mod;
        for(int i=2;i<=10000000;i++)invfac[i]=(long long)(mod-mod/i)*invfac[mod%i]%mod;
        for(int i=2;i<=10000000;i++)invfac[i]=(long long)invfac[i-1]*invfac[i]%mod;
    }
    inline int mul(int a,int b){return a * b % mod;}
    inline int inv(int x){return poly::ffpow(x,mod-2);}
    inline void main(){
        std::cin >> n >> m >> s;
        for (int i = 0; i <= m; i++) std::cin >> w[i];
        int t = std::min(m,n / s);
        init();
        for (int i = 0; i <= t; i++) 
            f[i] = poly::ffpow(m-i,n-i*s)*C(m,i)%mod*fac[n]%mod*inv(poly::ffpow(fac[s],i)*fac[n-i*s]%mod)%mod;
        for (int i = 0; i <= t; i++) a[i] = fac[i] * f[i] % mod;
        for (int i = 0; i <= t; i++) b[i]=(((i&1)?-1:1)*invfac[i]+mod)%mod;
        for (int i = 0; i <= t; i++)
            if(i < t - i) std::swap(a[i],a[t - i]);
        c = poly::mul(a,b,t,t); int ans = 0;
        for (int i = 0; i <= t; i++)
            ans = (ans + c[t-i] * w[i] % mod * invfac[i] % mod) % mod;
        std::cout << ans;
    }
}signed main(){wxy::main();return 0;}