### 题解

$$\left( \begin{array}{c} m\\k \end{array} \right) \left( \begin{array}{c} n\\ks \end{array} \right) \frac{(ks)!}{(s!)^k} (m-k)^{n-sk}$$

$$\left( \begin{array}{c} m\\k \end{array} \right) \sum_{i\geq k} (-1)^{i-k} \left( \begin{array}{c} m-k\\i-k \end{array} \right) \left( \begin{array}{c} n\\is \end{array} \right) \frac{(is)!}{(s!)^i} (m-i)^{n-si}$$

$$ans=\sum_{k=0}^{up} w_k \left( \begin{array}{c} m\\k \end{array} \right) \sum_{i\geq k} (-1)^{i-k} \left( \begin{array}{c} m-k\\i-k \end{array} \right) \left( \begin{array}{c} n\\is \end{array} \right) \frac{(is)!}{(s!)^i} (m-i)^{n-si}$$

$$\sum_{i=0}^{up} (-1)^i \left( \begin{array}{c} n\\is \end{array} \right) \frac{(is)!}{(s!)^i} (m-i)^{n-si} \sum_{k=0}^i w_k(-1)^{k} \left( \begin{array}{c} m\\k \end{array} \right) \left( \begin{array}{c} m-k\\i-k \end{array} \right)$$

$$\left( \begin{array}{c} m\\k \end{array} \right) \left( \begin{array}{c} m-k\\i-k \end{array} \right) =\frac{m!}{k!(i-k)!}$$

$$\sum_{i=0}^{up} (-1)^i \left( \begin{array}{c} n\\is \end{array} \right) \frac{(is)!}{(s!)^i} (m-i)^{n-si} \frac{m!}{(m-i)!} \sum_{k=0}^i \frac{w_k(-1)^{k}}{k!} \frac{1}{(i-k)!}$$

#include<bits/stdc++.h>
#define fo(i, a, b) for (Re int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (Re int i = (a); i >= (b); --i)
#define Re register
#define N 400005
#define mod 1004535809
#define ll long long
const double pi = acos(-1);
int R[N], L, len, n, m;
ll c1[N], c2[N], w[N], iw[N], invlen;
inline ll pow (ll x, int y)
{
ll ret = 1;
while (y)
{
if (y & 1) ret = ret * x % mod;
x = x * x % mod;
y >>= 1;
}
return ret;
}
inline void init ()
{
len = 1;
while (len <= m + m) len = len << 1, ++L;
invlen = pow(len, mod - 2);
for (int i = 0; i < len; ++i) R[i] = (R[i >> 1] >> 1) | ((i & 1) << L - 1);
w[0] = 1; w[1] = pow(3, (mod - 1) / len);
for (int i = 2; i < len; ++i) w[i] = w[i - 1] * w[1] % mod;
iw[0] = 1; iw[1] = pow(w[1], mod - 2);
for (int i = 2; i < len; ++i) iw[i] = iw[i - 1] * iw[1] % mod;
}
inline void ntt (ll *c, int len, bool opt)
{
for (int i = 0; i < len; ++i) if (i < R[i]) std::swap(c[i], c[R[i]]);
for (int l = 2; l <= len; l <<= 1)
{
int mid = l >> 1, now = len / l;
for (ll *p = c; p != c + len; p += l)
for (Re int i = 0; i < mid; ++i)
{
ll tmp = (opt ? w[now * i] : iw[now * i]) * p[mid + i] % mod;
p[mid + i] = (p[i] - tmp) % mod;
p[i] = (p[i] + tmp) % mod;
}
}
}
int s;
ll W[N], fac[10000005], invfac[10000005], ans;
int sgn (int x) {return x & 1 ? -1 : 1;}
ll C (int x, int y) {return fac[x] * invfac[y] % mod * invfac[x - y] % mod;}
int main()
{
scanf("%d %d %d", &n, &m, &s);
fo (i, 0, m) scanf("%lld", &W[i]);
invfac[0] = fac[0] = 1;
int q = std::max(n, m);
fo (i, 1, q) fac[i] = fac[i - 1] * i % mod;
invfac[q] = pow(fac[q], mod - 2);
fd (i, q - 1, 1) invfac[i] = invfac[i + 1] * (i + 1) % mod;
init();
fo (i, 0, m)
{
c1[i] = W[i] * sgn(i) * invfac[i] % mod;
c2[i] = invfac[i];
}
ntt(c1, len, 1);
ntt(c2, len, 1);
fo (i, 0, len) c1[i] = c1[i] * c2[i] % mod;
ntt(c1, len, 0);
fo (i, 0, len) c1[i] = c1[i] * invlen % mod;
int up = std::min(n / s, m);
fo (i, 0, up)
{
int si = s * i;
ans = (ans + sgn(i) * pow(m - i, n - si) * fac[m] % mod * invfac[m - i] % mod * C(n, si) % mod * fac[si] % mod * pow(invfac[s], i) % mod * c1[i] % mod) % mod;
}
printf("%lld", (ans + mod) % mod);
}