众所周知，小葱同学擅长计算，尤其擅长计算组合数。小葱现在希望你计算
$$ \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(k) \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
见下发文件。
子任务
对于所有测试数据：$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$ | 无 |