题目背景

1s 512M

题目描述

众所周知，小葱同学擅长计算，尤其擅长计算组合数。小葱现在希望你计算 $$\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_1k + a_2k^2 + \cdots + a_mk^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

5 1 10007 2
0 0 1

240

输入输出样例 #2

996 233 998244353 5
5 4 13 16 20 15

869469289

说明/提示

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

样例 3

见附加文件中 problem3.in 与 problem3.ans。

数据范围与提示

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

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

\begin{array}{|c|c|c|c|} \hline \textbf{测试点编号} & n\le & m\le & \textbf{其他特殊限制} \\ \hline 1\sim 3 & 1000 & 1000 & \\ \hline 4\sim 6 & 10^5 & 0 & p \textbf{是质数} \\ \hline 7\sim 8 & 10^9 & 0 & \\ \hline 9\sim 12 & 10^9 & 5 & \\ \hline 13\sim 16 & 10^9 & 1000 & x=1 \\ \hline 17\sim 20 & 10^9 & 1000 & \\ \hline \end{array}