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.


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


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
4 619
5 25 125 6
3 101
5 11 29
CPU Time limit 9 seconds
Memory limit 1024 MB
Statistics Show
License For educational use only

Please log in to submit a solution to this problem

Log in