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$.


hide comments
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

Added by:Francky
Date:2018-05-08
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All