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

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

$$\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\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$	$0$
$9\sim 12$	$10^9$	$5$
$13\sim 16$	$10^9$	$1000$	$x=1$
$17\sim 20$	$10^9$	$1000$