UOJ Logo Universal Online Judge

UOJ

#540. 【统一省选2020】组合数问题

统计

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

$$ \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, \cdots, a_m$。

输出格式

一行一个整数表示答案。

样例1

input

5 1 10007 2
0 0 1

output

240

explanation

$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$。

最终答案为:

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

样例2

input

996 233 998244353 5
5 4 13 16 20 15

output

869469289

样例3

见附加文件中 ex_problem3.inex_problem3.ans

数据范围

对于所有测试数据:$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$$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$

时间限制: $1\texttt{s}$

空间限制: $512\texttt{MB}$

附加数据下载