题目描述

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

题目大意

众所周知，斐波那契数列的公式如下：

$$F_i=\begin{cases}1&i=1\\2&i=2\\F_{i-1}+F_{i-2}&i\geqslant 3\end{cases} $$

定义 $p_i=\sum\limits_{j=1}^ka_j\times F_j^i$。现在给定 $k,m$ 以及 $\{p_i\}_{i=1}^k$，请求出 $p_{k+1}\bmod m$。

Translated by Eason_AC
2020.11.19

2
4 619
5 25 125 6
3 101
5 11 29

30
83

提示

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