Problem C
Captain Obvious and the Rabbit-Man
“It’s you, Captain Obvious!”—cried the evil
Rabbit-Man—“you came here to foil my evil plans!”
“Yes, it’s me.”—said Captain Obvious.
“But…how did you know that I would be here, on 625 Sunflower
Street?! Did you crack my evil code?”
“I did. Three days ago, you robbed a bank on 5 Sunflower
Street, the next day you blew up 25 Sunflower Street, and
yesterday you left quite a mess under number 125. These are all
powers of 5. And last year you pulled a similar stunt with
powers of 13. You seem to have a knack for Fibonacci numbers,
Rabbit-Man.”
“That’s not over! I will
learn…arithmetics!”—Rabbit-Man screamed as he was
dragged into custody—“You will never know what to
expect... Owww! Not my ears, you morons!”
“Maybe, but right now you are being arrested.”—Captain added
proudly.
Unfortunately, Rabbit-Man has now indeed learned some more advanced arithmetics. To understand it, let us define the sequence $F_ n$ (being not completely unlike the Fibonacci sequence):
\begin{align*} F_1 & = 1\\ F_2 & = 2\\ F_ n & = F_{n-1} + F_{n-2} \text { for $n \geq 3$.} \end{align*}Rabbit-Man has combined all his previous evil ideas into one master plan. On the $i$-th day, he does a malicious act on the spot number $p(i)$, defined as follows:
\begin{equation*} p(i) = a_1 \cdot F_1^ i + a_2 \cdot F_2^ i + \cdots + a_ k \cdot F_ k^ i\; . \end{equation*}The number $k$ and the integer coefficients $a_1, \ldots , a_ k$ are fixed. Captain Obvious learned $k$, but does not know the coefficients. Given $p(1), p(2), \ldots , p(k)$, help him to determine $p(k + 1)$. To avoid overwhelmingly large numbers, do all the calculations modulo a fixed prime number $M$. You may assume that $F_1 , F_2 , \ldots , F_ n$ are pairwise distinct modulo $M$. You may also assume 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 4\, 000$, $3 \leq M \leq 10^9$. The second line contains $k$ space-separated integers—the values of $p(1), p(2), \ldots , p(k)$ modulo $M$.
Output
Print the answers to the test cases in the order in which they appear in the input. For each test case print a single line containing one integer: the value of $p(k + 1)$ modulo $M$.
| Sample Input 1 | Sample Output 1 |
|---|---|
2 4 619 5 25 125 6 3 101 5 11 29 |
30 83 |