As is well known, Xiao Cong is good at calculation, especially at calculating binomial coefficients. Xiao Cong now wants you to calculate the value of:

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

where $n, x, p$ are given integers, and $f(k)$ is a given polynomial of degree $m$, $f(k) = a_0 + a_1 k + a_2 k^2 + \cdots + a_m k^m$.

$\binom n k$ is the binomial coefficient, defined as $\binom n k = \frac{n!}{k!(n-k)!}$.

Input

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

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

Output

Output a single integer representing the answer.

Examples

Input 1

5 1 10007 2
0 0 1

Output 1

240

Note 1

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

Since $x = 1$, $x^k$ is always $1$, so this term in 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$.

The final answer is:

$$ \sum_{k=0}^5 f(k) \times \binom 5 k = 0\times 1 + 1\times 5 + 4\times 10 + 9\times 10 + 16\times 5 + 25\times 1 = 240 $$

Input 2

996 233 998244353 5
5 4 13 16 20 15

Output 2

869469289

Input 3

See the provided files.

Subtasks

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

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