Problems
Captain Obvious and the Rabbit-Man
Captain Obvious and the Rabbit-Man
"\textit{It’s you, Captain Obvious!}" -- cried the evil Rabbit-Man -- "\textit{you came here to foil my evil plans!}"
"\textit{Yes, it’s me.}" -- said Captain Obvious.
"\textit{But... how did you know that I would be here, on 625 Sunflower Street?! Did you crack my evil code?}"
"\textit{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.}"
"\textit{That’s not over! I will learn... arithmetics!}" -- Rabbit-Man screamed as he was dragged into custody -- "\textit{You will never know what to expect... Owww! Not my ears, you morons!}"
"\textit{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 Fn (being not completely unlike the Fibonacci sequence):
\textbf{F_1 = 1,}
\textbf{F_2 = 2,}
\textbf{F_n = F_\{n−1\} + F_\{n−2\} }for\textbf{ n ≥ 3.}
Rabbit-Man has combined all his previous evil ideas into one master plan. On the \textbf{i}-th day, he does a malicious act on the spot number \textbf{p(i)}, defined as follows:
\textbf{p(i) = a_1 · F^i_1 + a_2 · F^i_2 + ... + a_k · F^i_k}.
The number \textbf{k} and the integer coefficients \textbf{a_1}, ..., \textbf{a_k} are fixed. Captain Obvious learned \textbf{k}, but does not know the coefficients. Given \textbf{p(1)}, \textbf{p(2)}, ..., \textbf{p(k)}, help him to determine \textbf{p(k+1)}. To avoid overwhelmingly large numbers, do all the calculations modulo a fixed prime number \textbf{M}. You may assume that \textbf{F_1}, \textbf{F_2}, ..., \textbf{F_n} are pairwise distinct modulo \textbf{M}. You may also assume that there always exists a unique solution for the given input.
\InputFile
The first line of input contains the number of test cases \textbf{T}. The descriptions of the test cases follow:
The first line of each test case contains two integers \textbf{k} and \textbf{M}, \textbf{1} ≤ \textbf{k} ≤ \textbf{4000}, \textbf{3} ≤ \textbf{M} ≤ \textbf{10^9}. The second line contains \textbf{k }space-separated integers -- the values of \textbf{p(1)}, \textbf{p(2)}, ..., \textbf{p(k)} modulo \textbf{M}.
\OutputFile
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 \textbf{p(k+1)} modulo \textbf{M}.
\textit{\textbf{Explanation}}: the first sequence is simply \textbf{5^i} \textbf{mod} \textbf{619}, therefore the next element is \textbf{5^5} \textbf{mod} \textbf{619 = 30}. The second sequence is \textbf{2 · 1^i + 3^i mod 101}.
Input example #1
2 4 619 5 25 125 6 3 101 5 11 29
Output example #1
30 83