众所周知，小葱同学擅长计算，尤其擅长计算组合数。小葱现在希望你计算
$(\sum_{k=0}^{n}f(k)\times x^k \times \begin{pmatrix}n \\ k \end{pmatrix}) mod\ p$
的值。其中 $n, x, p$ 为给定的整数，$f(k)$ 为给定的一个 $m$ 次多项式$f(k) = a_0 + a_1k + a_2k^2 + · · · + a_mk^m$。 $\begin{pmatrix}n \\ k \end{pmatrix}$为组合数，其值为$\begin{pmatrix}n \\ k \end{pmatrix}=\frac{n!}{k!(n-k)!}$

第一行四个非负整数 $n, x, p, m$。
第二行 $m + 1$ 个整数，分别代表 $a_0, a_1, · · · , a_m$。

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

【样例 1 解释】
$f(0) = 0，f(1) = 1，f(2) = 4，f(3) = 9，f(4) = 16，f(5) = 25$。
$x = 1$，故 $x^k$ 恒为 1，乘积中的该项可以忽略。
$\begin{pmatrix}5 \\ 0 \end{pmatrix}=1$，$\begin{pmatrix}5 \\ 1 \end{pmatrix}=5$，$\begin{pmatrix}5 \\ 2 \end{pmatrix}=10$，$\begin{pmatrix}5 \\ 4 \end{pmatrix}=5$，$\begin{pmatrix}5 \\ 5 \end{pmatrix}=1$。
最终答案为：
$(\sum_{k=0}^{5}f(k) \times \begin{pmatrix}5 \\ k \end{pmatrix}) =0 × 1 + 1 × 5 + 4 × 10 + 9 × 10 + 16 × 5 + 25 × 1 = 240$
【数据范围】
对于所有测试数据：$1 ≤ n, x, p ≤ 10^9,0 ≤ a_i ≤ 10^9,0 ≤ m ≤ min(n,1000)$。
每个测试点的具体限制见下表：