"\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}.