$$ a _ i k ^ i = a _ i \sum _ {j = 0} ^ i {i \brace j} k ^ {\underline j} $$
将 $a _ i$ 贡献到每个位置，得到
$$ b _ i = \sum _ {j = i} ^ m {j \brace i} a _ j $$
那么
$$ \begin {aligned} ANS & = \sum _ {k = 0} ^ n \binom n k x ^ k\sum _ {i = 0} ^ m b _ i k ^ {\underline i} \\ & = \sum _ {i = 0} ^ m b _ i i!\sum _ {k = 0} ^ n \binom n k \binom k i x ^ k \\ & = \sum _ {i = 0} ^ m b _ i i! \sum _ {k = 0} ^ n \binom n i \binom {n - i} {k -i} x ^ k \\ & = \sum _ {i = 0} ^ m b _ i i! \binom n i \sum _ {k = 0} ^ {n - i} \binom {n - i} k x ^ {k + i} \\ & = \sum _ {i = 0} ^ m b _ i n ^ {\underline i} x ^ i \sum _ {k = 0} ^ {n - i} \binom {n - i} k x ^ k \\ & = \sum _ {i = 0} ^ m b _ i n ^ {\underline i} x ^ i (x + 1) ^ {n - i} \\ \end {aligned} $$
#include<cstdio> usingnamespace std; template <classType> voidread(Type &x) { char c; bool flag = false; while ((c = getchar()) < '0' || c > '9') c == '-' && (flag = true); x = c - '0'; while ((c = getchar()) >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0'; if (flag) x = ~x + 1; } template <classType, class ...rest> voidread(Type &x, rest &...y){ read(x), read(y...); } template <classType> voidwrite(Type x) { if (x < 0) putchar('-'), x = ~x + 1; if (x > 9) write(x / 10); putchar(x % 10 + '0'); } typedeflonglong LL; constint N = 5e3 + 10; int n, x, p, m, f[N], g[N], s[N][N]; voidinit() { s[0][0] = 1; for (int i = 1; i <= m; ++i) for (int j = 1; j <= m; ++j) s[i][j] = (s[i - 1][j - 1] + (LL)j * s[i - 1][j]) % p; } intbinpow(int b, int k) { int res = 1; for (; k; k >>= 1, b = (LL)b * b % p) if (k & 1) res = (LL)res * b % p; return res; } intmain() { read(n, x, p, m); init(); for (int i = 0; i <= m; ++i) read(f[i]); for (int i = 0; i <= m; ++i) for (int j = i; j <= m; ++j) g[i] = (g[i] + (LL)s[j][i] * f[j]) % p; int res = 0; for (int i = 0, t = 1; i <= m; t = (LL)t * (n - i++) % p * x % p) res = (res + (LL)g[i] * t % p * binpow(x + 1, n - i)) % p; write((res + p) % p); return0; }