캡틴 오브비어스와 래빗맨

"너였구나, 캡틴 오브비어스!" 악당 래빗맨이 소리쳤다. "내 계획을 망치러 왔군!"
"그래, 나다." 캡틴 오브비어스가 답했다.
"그런데 내가 해바라기 거리 625번지에 있을 줄 어떻게 알았지? 내 암호를 풀었나?"
"풀었다. 사흘 전에 너는 해바라기 거리 5번지에서 은행을 털었고, 다음 날 25번지를 폭파했고, 어제는 125번지를 쑥대밭으로 만들었다. 모두 5의 거듭제곱이다. 작년에는 13의 거듭제곱으로 똑같은 짓을 했다. 래빗맨, 너는 피보나치 수를 참 좋아하는군."
"아직 안 끝났어! 내가 산수를 배워서..." 붙잡혀 끌려가며 래빗맨이 외쳤다. "다음에는 아무도 예측하지 못할 거다. 아악! 귀는 잡지 마, 멍청이들아!"
"그럴지도. 하지만 지금 너는 체포됐다." 캡틴이 자랑스럽게 덧붙였다.

불행히도 래빗맨은 그 뒤로 더 고급 산수를 익혔다. 그 내용을 설명하려면 먼저 피보나치 수열과 비슷한 수열 $F_n$을 정의해야 한다.

$F_1 = 1, \quad F_2 = 2, \quad F_n = F_{n-1} + F_{n-2} \ (n \ge 3)$

래빗맨은 예전 계획을 모두 하나로 합쳤다. $i$번째 날에는 다음 식으로 정해지는 $p(i)$번지에서 범행을 저지른다.

$p(i) = a_1 F_1^i + a_2 F_2^i + \dots + a_k F_k^i$

$k$와 정수 계수 $a_1, \dots, a_k$는 고정되어 있다. 캡틴 오브비어스는 $k$는 알아냈지만 계수는 모른다. $p(1), p(2), \dots, p(k)$가 주어질 때 $p(k+1)$을 구해서 캡틴을 도와라. 수가 너무 커지지 않도록 모든 계산은 고정된 소수 $M$으로 나눈 나머지에서 한다. $F_1, F_2, \dots, F_k$는 $M$으로 나눈 나머지가 서로 다르다고 가정해도 된다. 또 주어진 입력의 답은 항상 유일하다고 가정해도 된다.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스는 두 줄로 이루어진다.

첫 줄에는 두 정수 $k$와 $M$이 주어진다 ($1 \le k \le 4000$, $3 \le M \le 10^9$, $M$은 소수). 둘째 줄에는 $p(1), p(2), \dots, p(k)$를 $M$으로 나눈 나머지 $k$개가 공백으로 구분되어 주어진다.

각 테스트 케이스마다 $p(k+1)$을 $M$으로 나눈 나머지를 한 줄에 하나씩, 입력에 주어진 순서대로 출력한다. 나머지는 $0$ 이상 $M-1$ 이하의 값으로 출력한다.

첫 번째 테스트 케이스의 수열은 $p(i) = 5^i \bmod 619$이므로 다음 항은 $5^5 \bmod 619 = 30$이다. 두 번째 테스트 케이스의 수열은 $p(i) = 2 \times 1^i + 3^i \bmod 101$이다.