Description

As everyone knows, student Xiaocong is good at calculations, especially at computing binomial coefficients. Now Xiaocong wants you to compute

$$\left(\sum_{k=0}^{n}f(k)\times x^k\times \binom{n}{k}\right)\bmod p$$

where $n$, $x$, and $p$ are given integers, and $f(k)$ is a given degree $m$ polynomial $f(k) = a_0 + a_1k + a_2k^2 + \cdots + a_mk^m$. $\binom{n}{k}$ is the binomial coefficient, defined as $\binom{n}{k} = \frac{n!}{k!(n-k)!}$.

Input Format

The first line contains four non-negative integers $n$, $x$, $p$, $m$.

The second line contains $m + 1$ integers, representing $a_0$, $a_1$, $\cdots$, $a_m$.

Output Format

Output one integer in a single line, which is the answer.

5 1 10007 2
0 0 1

240

996 233 998244353 5
5 4 13 16 20 15

869469289

Hint

Sample 1 Explanation

$f(0) = 0，f(1) = 1，f(2) = 4，f(3) = 9，f(4) = 16，f(5) = 25$.

$x = 1$, so $x^k$ is always $1$, and this factor in each term of the product can be ignored.

$\binom 5 0 = 1, \binom 5 1 = 5, \binom 5 2 = 10, \binom 5 3 = 10, \binom 5 4 = 5, \binom 5 5 = 1$.

Sample 3

See the attached files problem3.in and problem3.ans.

Constraints and Hints

For all testdata: $1\le n, x, p \le 10^9, 0\le a_i\le 10^9, 0\le m \le \min(n,1000)$.

The specific limits for each test point are shown in the table below:

Test Point ID	$n\le$	$m\le$	Other Special Limits
$1\sim 3$	$1000$
$4\sim 6$	$10^5$	$0$	$p$ is prime.
$7\sim 8$	$10^9$
$9\sim 12$		$5$
$13\sim 16$		$1000$	$x=1$
$17\sim 20$

Translated by ChatGPT 5