## CERI2018H - Polynomial evaluation

no tags

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$. wisfaq: 2018-05-08 14:13:54 The modulo's in the explanation aren't formatted correctly. Probably a Tex problem. =(Francky)=> Thanks ; fixed. Last edit: 2018-05-08 14:54:36