#3300. 「联合省选 2020 A」组合数问题

题目描述
众所周知，小葱同学擅长计算，尤其擅长计算组合数。小葱现在希望你计算

$$\left(\sum_{k=0}^n f(k) \times x^k \times \binom n k\right) \bmod p $$

的值。其中 $n, x, p$ 为给定的整数， $f(k)$ 为给定的一个 $m$ 次多项式 $f(k) = a_0 + a_1 k + a_2 k^2 + \cdots + a_m k^m$ 。

$\binom n k$ 为组合数，其值为 $\binom n k = \frac{n!}{k!(n-k)!}$ 。

输入格式
第一行四个非负整数 $n, x, p, m$ 。
第二行 $m + 1$ 个整数，分别代表 $a_0, a_1, \dots, a_m$ 。

输出格式
仅一行一个整数表示答案。

样例 1

输入

5 1 10007 2
0 0 1

输出

解释：

$f(0) = 0$ ， $f(1) = 1$ ， $f(2) = 4$ ， $f(3) = 9$ ， $f(4) = 16$ ， $f(5) = 25$
$x = 1$ ，故 $x^k$ 恒为 $1$
$\binom 5 0 = 1, \binom 5 1 = 5, \binom 5 2 = 10, \binom 5 3 = 10, \binom 5 4 = 5, \binom 5 5 = 1$
最终答案为：$0\times 1 + 1\times 5 + 4\times 10 + 9\times 10 + 16\times 5 + 25\times 1 = 240$

样例 2

输入

996 233 998244353 5
5 4 13 16 20 15

输出

869469289

数据范围与提示

对于所有测试数据：$1\le n, x, p \le 10^9, 0\le a_i\le 10^9, 0\le m \le \min(n,1000)$。

每个测试点的具体限制见下表：

测试点编号	$n\le$	$m\le$	其他特殊限制
1$\sim$3	$1000$
4$\sim$6	$10^5$	$0$	$p$ 是质数
7$\sim$8	$10^9$
9$\sim$12		$5$
13$\sim$16	$1000$		$x=1$
17$\sim$20

#L3300. 「联合省选 2020 A」组合数问题