3. 组合数问题

【题目描述】

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

$$\left(\sum_{k=0}^nf(k)\times x^k\times C_n^k\right) \mod p$$

的值。其中 $n,x,p$ 为给定的整数，$f(k)$ 为给定的一个 $m$ 次多项式 $f(k)=a_0+a_1k+a_2k^2+\cdots+a_mk^m$。$C_n^k$ 为组合数，其值为 $C_n^k=\frac{n!}{k!(n-k)!}$。

【输入格式】

第一行四个非负整数 $n,x,p,m$。

第二行 $m + 1$ 个整数，分别代表 $a_0,a_1,\cdots,a_m$。

【输出格式】

仅一行一个整数表示答案。

【样例1输入】

5 1 10007 2
0 0 1

【样例1输出】

240

【样例1解释】

$f(0) = 0，f(1) = 1，f(2) = 4，f(3) = 9，f(4) = 16，f(5) = 25$。

$x=1$,故 $x^k$ 恒为 1，乘积中的该项可以忽略。

$C_5^0=1,C_5^1=5,C_5^2=10,C_5^3=10,C_5^4=5,C_5^5=1$。

最终答案为：

$\sum_{k=0}^5f(k)\times C_5^k = 0 × 1 + 1 × 5 + 4 × 10 + 9 × 10 + 16 × 5 + 25 × 1 = 240$

【样例2输入】

996 233 998244353 5
5 4 13 16 20 15

【样例2输出】

869469289

【样例3】

点击下载样例3

【提示】

评测时请使用 -O2 评测机。

对于所有测试数据：$1 ≤ n,x,p ≤ 10^9，0 ≤ a_i ≤ 10^9 ，0 ≤ m ≤ min(n,1000)$。每个测试点的具体限制见下表：

【来源】

HAOI2020 Day1 Task2