Description

“是你，显而易见船长！”邪恶的兔子人喊道，“你来这里是为了阻止我的邪恶计划！”

“是的，是我。”显而易见船长说道。

“但是……你怎么知道我会在向日葵街 625 号？！你破解了我的邪恶代码吗？”

“我破解了。三天前，你抢劫了向日葵街 5 号的银行，第二天你炸毁了向日葵街 25 号，昨天你在 125 号制造了一场混乱。这些都是 5 的幂。而去年你用 13 的幂做了类似的事情。你似乎对斐波那契数有一种天赋，兔子人。”

“这还没完！我会学习……算术！”兔子人被拖入拘留时尖叫道，“你永远不知道会发生什么……哎哟！别碰我的耳朵，你们这些笨蛋！”

“也许吧，但现在你被捕了。”船长自豪地补充道。

不幸的是，兔子人现在确实学会了一些更高级的算术。为了理解它，让我们定义序列 $F_n$（与斐波那契序列不完全相似）：

$F_{1} = 1$，

$F_{2} = 2$，

$F_{n} = F_{n-1} + F_{n-2}$ 对于 $n \ge 3$。

兔子人将他所有以前的邪恶想法结合成一个总计划。在第 $i$ 天，他在编号为 $p(i)$ 的地方进行恶意行为，定义如下：

$p(i) = a_{1}\cdot F_{1}^{i} + a_{2}\cdot F_{2}^{i} + \cdots + a_{k}\cdot F_{k}^{i}$。

数字 $k$ 和整数系数 $a_1 , \cdots , a_k$ 是固定的。显而易见船长知道 $k$，但不知道系数。给定 $p(1), p(2), \cdots, p(k)$，帮助他确定 $p(k + 1)$。为了避免过大的数字，所有计算都在一个固定的素数 $M$ 模下进行。你可以假设 $F_1, F_2, \cdots, F_n$ 在模 $M$ 下是两两不同的。你也可以假设给定的输入总是存在唯一解。

Input Format

输入的第一行包含测试用例的数量 $T$。接下来的每个测试用例描述如下：

每个测试用例的第一行包含两个整数 $k$ 和 $M$，其中 $1 \le k \le 4000, 3 \le M \le 10^{9}$。第二行包含 $k$ 个以空格分隔的整数——$p(1), p(2), \cdots, p(k)$ 模 $M$ 的值。

Output Format

按照输入中出现的顺序打印测试用例的答案。对于每个测试用例，打印一行包含一个整数：$p(k + 1)$ 模 $M$ 的值。

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

30
83

Hint

时间限制：6 秒，内存限制：128 MB。

题面翻译由 ChatGPT-4o 提供。