The goal of the problem is to evaluate some polynomial expressions.

$$P(x) = a_0 x^d + a_1 x^{d-1} + a_2 x^{d-2} + \cdots + a_{d-1} x^1 + a_{d} x^0$$

Input

The first line of the input consist of a single integer number t which determines the number of tests.

Each test is on two separate lines.

In each test,

• on the first line, there is three integer numbers $d$, $x$, and $m$.

• on the second line, there is $d+1$ integer numbers $a_i$ .

Constraints

• $0 < t \leqslant 400$ ;
• $0 \leqslant d \leqslant 1000$ ;
• $\mid x \mid \leqslant 10^9$ ;
• $\mid a_i \mid \leqslant 10^9$ ;
• $1 < m \leqslant 2\times10^9$.

Output

For each test case, print $P(x) \pmod m$.

Example

Input:
3
0 3 1000
4321
3 10 1000000000
2 0 1 8
5 123456789 1000000007
-1 1 -1 1 -1 1

Output:
321
2018
715709281

Explanation

For the first test case, $P(x) = 4321$, $P$ is a constant polynomial, and $P(3) \pmod {1000} = 321$.

For the second test case, $P(x) = 2x^3 + x + 8$, and $P(10) \pmod {1000000000} = 2018$.

For the third test case, $P(x) = -x^5 + x^4 - x^3 + x^2 - x +1$.