好坑啊不开心……
其实这题的想法还是比较简单粗暴的。题目明示恰好xxx，显然排除斜率二分这个玩意儿，那么不就只剩下容斥了嘛……
令 \(A_{x}\) 为恰好出现了 \(S\) 次的至少有 \(x\) 种的方案数， \({B_{x}}\) 为恰好出现了\(S\) 次的颜色恰好 \(x\) 种的方案数。\(A_{x}\) 可以 \(O(1)\) 求得，\(A_{x} = \frac{\binom{n}{S * x} * (m - x) ^ {n - S * x} * (S * i)!}{(S!)^{x}}\)。（为了方便描述，我们在下面所说的颜色均为满足恰好出现 \(S\) 次的颜色）。
那么，一个恰好有 \(x\) 种颜色的方案对答案的贡献应该为
（我们先只考虑颜色种数恰好为 \(k\) 的）
\(g_{x} = [x = k] = \sum_{i = 0}^{x}\binom{x}{i}f_{i}\)
（\(f_{i}\) 为容斥系数）
二项式反演，得
\(f_{x} = \binom{k}{x} * (-1) ^ {k - x}\)
所以令 \(B_{x}\) 为恰好 \(x\) 种颜色的方案数，有：
\(B_{x} = \sum_{i = 0}^{m}\binom{m}{i}*A_{i}*\binom{i}{x}*(-1)^{i - x}\)
由于有 \(m\) 个\(B_{x}\) 要求值，且明显的给了一个NTT模数，
考虑转化成卷积的形式：
（把与各种变量相关的尽量整理到一起）
得到：\(B_{x} = \frac{(-1)^{-x}}{x!}\sum_{i = 0}^{m}\frac{\binom{m}{i}*(-1)^{i}}{(i - x)!}\)
前面的是个常数，后面的是一个卷积（把 \(i - x\) 先 \(+ m\) 再反转（防止爆负））……上NTT就好了。
但这还没完！预处理逆元、阶乘逆元、阶乘的话会容易TLE！所以应该快速幂暴力处理逆元……(；′⌒`)
#include <bits/stdc++.h>
using namespace std;
#define maxn 10000005
#define mod 1004535809
#define int long long
int n, m, M, S, W[maxn], G[maxn], a[maxn], b[maxn], c[maxn];
int ans, K, fac[maxn], A[maxn], B[maxn];
int lim = , len, rev[maxn]; int read()
{
int x = , k = ;
char c; c = getchar();
while(c < '' || c > '') { if(c == '-') k = -; c = getchar(); }
while(c >= '' && c <= '') x = x * + c - '', c = getchar();
return x * k;
} int Up(int x) { if(x >= mod) x -= mod; return x; }
int Down(int x) { if(x < ) x += mod; return x; }
int Mod(int x) { x %= mod; if(x < ) x += mod; return x; }
int Qpow(int x, int timer)
{
int base = ;
for(; timer; timer >>= , x = x * x % mod)
if(timer & ) base = x * base % mod;
return base;
}
#define inv(x) Qpow(x, mod - 2) int C(int n, int m)
{
if(n < m || n < || m < ) return ;
int t = fac[n] * inv(fac[m]) % mod * inv(fac[n - m]) % mod;
return t;
} void init()
{
fac[] = ;
int t = max(n, m);
for(int i = ; i <= t; i ++) fac[i] = fac[i - ] * i % mod;
} void Pre()
{
for(int i = ; i <= m; i ++)
{
if(S * i > n) break;
int t = S * i, t1 = C(n, t) * fac[t] % mod;
A[i] = t1 * Qpow(inv(fac[S]), i) % mod * Qpow(m - i, n - t) % mod;
}
for(int i = ; i <= m; i ++)
a[i] = C(m, i) * A[i] % mod * fac[i] % mod * Qpow(-, i) % mod;
for(int i = -m; i <= m; i ++) c[i + K] = i < ? : inv(fac[i]);
for(int i = ; i <= M; i ++) b[i] = c[M - i];
} void NTT(int *A, int opt)
{
int t = opt < ? Qpow(, mod - ) : ;
for(int i = ; i < lim; i ++)
if(i < rev[i]) swap(A[i], A[rev[i]]); for(int l = ; l < lim; l <<= )
{
int g = Qpow(t, (mod - ) / (l << ));
for(int i = ; i < l; i ++) G[i] = 1ll * G[i - ] * g % mod;
for(int i = ; i < lim; i += (l << ))
for(int j = i; j <= i + l - ; j ++)
{
int x = A[j], y = 1ll * G[j - i] * A[j + l] % mod;
A[j] = Up(x + y); A[j + l] = Down(x - y);
}
}
} signed main()
{
n = read(), m = read(), S = read(); K = m, M = m * + ;
for(int i = ; i <= m; i ++) W[i] = read();
init(), Pre(); G[] = ;
while(lim <= M + m) lim <<= , len ++;
for(int i = ; i < lim; i ++)
rev[i] = (rev[i >> ] >> ) | ((i & ) << ((len - )));
NTT(a, ), NTT(b, );
for(int i = ; i < lim; i ++) a[i] = a[i] * b[i] % mod;
NTT(a, -); int inv1 = Qpow(lim, mod - );
for(int i = ; i <= m; i ++)
{
int t = ((i & ) ? - : ) * inv(fac[i]) % mod * W[i] % mod;
ans = Mod(ans + a[i + m + ] * inv1 % mod * t % mod);
}
printf("%lld\n", ans);
return ;
}