You are given the first $2K$ integers $a_0, a_1, \ldots, a_{2K-1}$ (modulo $M$) of an infinite integer sequence $(a_i)_{i=0}^{\infty}$ that satisfies an integer-coefficient linear recurrence relation of order $K$.

That is, they satisfy $$ a_n = \sum_{i=1}^{K} c_i a_{n-i} $$ for $n \ge K$, where $c_1, \ldots, c_K$ are integer constants.

Find $a_{2K}$ modulo $M$.

Input

The first line contains $T$ ($1 \le T \le 4000$), the number of test cases.

Each test case consists of two lines:

• First line contains $K$ ($1 \le K \le 50$) and $M$ ($1 \le M < 2^{31}$).
• Next line contains $2K$ integers $a_0, a_1, \ldots, a_{2K-1}$ (modulo $M$).

Note: $M$ is not necessarily a prime.

Output

For each test case, output $a_{2K}$ modulo $M$.

Example

Input

6
1 16
4 8
1 10
4 8
2 64
13 21 34 55
2 27
13 21 7 1
3 1000000007
32 16 8 4 2 1
2 64
13 21 34 56

Output

0
6
25
8
500000004
40