Капітан Очевидність і Людина-Кролик: загадка#6775

Капітан Очевидність і Людина-Кролик: загадка

1 секунда

256 мегабайтів

Легка

"Це ти, Капітане Очевидність!" – закричав Людина-Кролик – "ти прийшов сюди, щоб зірвати мої плани!"

"Так, це я." – сказав Капітан Очевидність.

"Але... як ти дізнався, що я буду тут, у секретному притулку під номером 625?! Ти розгадав мій загадковий код?"

"Так. Три дні тому твої підказки вказували на місце 5, наступного дня — на 25, а вчора — на 125 — усе це ступені 5. А минулого року така ж закономірність була для числа 13. Здається, всі твої загадки стосуються певних числових послідовностей, Людино-Кролик."

"Це ще не кінець! Я навчуся... арифметики!" – закричав Людина-Кролик, коли його відтягували – "Ти ніколи не знатимеш, чого очікувати... Ой! Тільки не мої вуха!"

"Можливо, але зараз тебе спіймали." – з гордістю додав Капітан.

На жаль, Людина-Кролик справді засвоїв більш просунуту арифметику. Щоб це зрозуміти, визначимо послідовність $F_{n}$ F_n (не зовсім як Фібоначчі):

$F_{1} = 1,$ F_1 = 1,

$F_{2} = 2,$ F_2 = 2,

$F_{n} = F_{n - 1} + F_{n - 2}$ F_n = F_{n-1} + F_{n-2} для $n \geq 3.$ n \ge 3.

Людина-Кролик об'єднав усі свої старі головоломки в одну нову суперзагадку. У $i$ -й день він вказує на місце $p (i)$ , яке визначається так:

$p (i) = a_{1} \cdot F_{1}^{i} + a_{2} \cdot F_{2}^{i} + ... + a_{k} \cdot F_{k}^{i} .$ p(i) = a_1 \cdot F_1^i + a_2 \cdot F_2^i + ... + a_k \cdot F_k^i.

Число $k$ та цілі коефіцієнти $a_{1}, \dots, a_{k}$ a_1, \ldots, a_k є фіксованими. Капітан Очевидність дізнався $k$ , але не знає коефіцієнтів. Знаючи $p (1), p (2), \dots, p (k)$ p(1), p(2), \ldots, p(k), допоможіть йому визначити $p (k + 1)$ p(k+1). Щоб уникнути великих чисел, проведіть всі обчислення за модулем заданого простого числа $M$ . Вважайте, що $F_{1}, F_{2}, \dots, F_{n}$ F_1, F_2, \ldots, F_n попарно різні за модулем $M$ і для вхідних даних завжди існує єдиний розв'язок.

Вхідні дані

Перший рядок містить число тестів $T$ . Далі наведено описи тестів:

Перший рядок кожного тесту містить два цілі числа $k$ та $M$ , $1 \leq k \leq 4000$ 1 \le k \le 4000, $3 \leq M \leq 1 0^{9}$ 3 \le M \le 10^9. Другий рядок містить $k$ цілих чисел — значення $p (1), p (2), \dots, p (k)$ p(1), p(2), \ldots, p(k) за модулем $M$ .

Вихідні дані

Виведіть відповіді для усіх тестів у порядку їх подання. Для кожного тесту виведіть у окремому рядку одне ціле число: значення $p (k + 1)$ p(k+1) за модулем $M$ .

Пояснення: перша послідовність — це просто $5^{i}$ 5^i $mod$ $619$ , отже наступний елемент $5^{5}$ 5^5 $\mod$ $619 = 30$ 619 = 30. Друга послідовність — $2 \cdot 1^{i} + 3^{i} mod 101$ 2 \cdot 1^i + 3^i \mod 101.

Приклади

Приклад 1