Captain Obvious and Rabbit-Man: The Riddle#6775

Captain Obvious and Rabbit-Man: The Riddle

1 second

256 megabytes

Easy

"It's you, Captain Obvious!" – cried Rabbit-Man – "you came here to foil my plans!"

"Yes, it's me." – said Captain Obvious.

"But... how did you know that I would be here, at the secret hideout marked 625?! Did you crack my mysterious code?"

"I did. Three days ago, your clues pointed to location 5, the next day to 25, and yesterday to 125—all powers of 5. And last year the same pattern, but with 13. It seems your puzzles are all about certain number sequences, Rabbit-Man."

"That's not the end! I will learn... arithmetics!" – Rabbit-Man screamed as he was dragged away – "You will never know what to expect... Owww! Not my ears!"

"Maybe, but right now you are being caught." – Captain added proudly.

Unfortunately, Rabbit-Man has indeed learned some more advanced arithmetics. To understand it, let us define the sequence $F_{n}$ F_n (not completely unlike the Fibonacci sequence):

$F_{1} = 1,$ F_1 = 1,

$F_{2} = 2,$ F_2 = 2,

$F_{n} = F_{n - 1} + F_{n - 2}$ F_n = F_{n-1} + F_{n-2} for $n \geq 3.$ n \ge 3.

Rabbit-Man has combined all his old puzzle ideas into a new master riddle. On the $i$ -th day, he points to location number $p (i)$ , defined as follows:

$p (i) = a_{1} \cdot F_{1}^{i} + a_{2} \cdot F_{2}^{i} + ... + a_{k} \cdot F_{k}^{i} .$ p(i) = a_1 \cdot F_1^i + a_2 \cdot F_2^i + ... + a_k \cdot F_k^i.

The number $k$ and the integer coefficients $a_{1}, \dots, a_{k}$ a_1, \ldots, a_k are fixed. Captain Obvious has found $k$ , but not the coefficients. Given $p (1), p (2), \dots, p (k)$ p(1), p(2), \ldots, p(k), help him to determine $p (k + 1)$ p(k+1). To avoid large numbers, perform all calculations modulo a given prime number $M$ . You may assume $F_{1}, F_{2}, \dots, F_{n}$ F_1, F_2, \ldots, F_n are pairwise distinct modulo $M$ , and that there always exists a unique solution for the given input.

Input

The first line of input contains the number of test cases $T$ . The descriptions of the test cases follow:

The first line of each test case contains two integers $k$ and $M$ , $1 \leq k \leq 4000$ 1 \le k \le 4000, $3 \leq M \leq 1 0^{9}$ 3 \le M \le 10^9. The second line contains $k$ space-separated integers – the values of $p (1), p (2), \dots, p (k)$ p(1), p(2), \ldots, p(k) modulo $M$ .

Output

Print the answers to the test cases in the order they appear in the input. For each test case print a single line containing one integer: the value of $p (k + 1)$ p(k+1) modulo $M$ .

Explanation: the first sequence is simply $5^{i}$ 5^i $mod$ $619$ , therefore the next element is $5^{5}$ 5^5 $\mod$ $619 = 30$ 619 = 30. The second sequence is $2 \cdot 1^{i} + 3^{i} mod 101$ 2 \cdot 1^i + 3^i \mod 101.

Examples

Example 1