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

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: EntropyIncreaser

题目描述

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

\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

样例输出 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 ,乘积中的该项可以忽略。

\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

996 233 998244353 5
5 4 13 16 20 15

样例输出 2

869469289

样例 3

见附加文件中 problem3.inproblem3.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
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