众所周知，小葱同学擅长计算，尤其擅长计算组合数。小葱现在希望你计算
\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 。
仅一行一个整数表示答案。
5 1 10007 2 0 0 1
240
对于所有测试数据： 1\le n, x, p \le 10^9, 0\le a_i\le 10^9, 0\le m \le \min(n,1000) 。
每个测试点的具体限制见下表：