P7016 [CERC2013] 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): $F_{1} = 1$ , $F_{2} = 2$ , $F_{n} = F_{n-1} + F_{n-2}$ for $n \ge 3$ . 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: $p(i) = a_{1}·F_{1}^{i} + a_{2}·F_{2}^{i} + \cdots + a_{k}·F_{k}^{i}.$ The number $k$ and the integer coefficients $a_1 , \cdots $ , ak are fixed. Captain Obvious learned $k$ , but does not know the coefficients. Given $p(1) , p(2) , \cdots , 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 , \cdots , 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 \le k \le 4000 , 3 \le M \le 10^{9}.$ The second line contains $k$ space-separated integers $-$ the values of $p(1) , p(2) , \cdots , 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$ .

Time limit: 6 s, Memory limit: 128 MB.