Капітан Очевидність і Людина-Кролик
"Це ти, Капітан Очевидність!" — закричав злий Кролик-Людина. — "Ти прийшов сюди, щоб зірвати мої злі плани!"
"Так, це я." — відповів Капітан Очевидність.
"Але... як ти дізнався, що я буду тут, на Соняшниковій вулиці, 625?! Ти розгадав мій злий код?"
"Так. Три дні тому ти пограбував банк на Соняшниковій вулиці, 5, наступного дня ти підірвав Соняшникову вулицю, 25, а вчора ти залишив безлад під номером 125. Це все ступені 5. І минулого року ти вчинив подібний трюк зі ступенями 13. Ти, здається, маєш схильність до чисел Фібоначчі, Кролик-Людина."
"Це ще не кінець! Я вивчу... арифметику!" — закричав Кролик-Людина, коли його тягнули в наручниках. — "Ти ніколи не дізнаєшся, чого очікувати... Ой! Не за вуха, ви, дурні!"
"Можливо, але зараз ти заарештований." — додав Капітан з гордістю.
На жаль, Кролик-Людина тепер дійсно вивчив деяку більш просунуту арифметику. Щоб зрозуміти це, давайте визначимо послідовність Fn (яка не зовсім не схожа на послідовність Фібоначчі):
F_1 = 1,
F_2 = 2,
F_n = F_{n−1} + F_{n−2} для n ≥ 3.
Кролик-Людина об'єднав усі свої попередні злі ідеї в один майстер-план. На i-й день він здійснює злий вчинок на місці номер p(i), визначеному наступним чином:
p(i) = a_1 · F^i_1 + a_2 · F^i_2 + ... + a_k · F^i_k.
Число k та цілі коефіцієнти a_1, ..., a_k є фіксованими. Капітан Очевидність дізнався k, але не знає коефіцієнтів. Дано p(1), p(2), ..., p(k), допоможіть йому визначити p(k+1). Щоб уникнути надмірно великих чисел, виконуйте всі обчислення за модулем фіксованого простого числа M. Ви можете припустити, що F_1, F_2, ..., F_n є попарно різними за модулем M. Ви також можете припустити, що завжди існує унікальне рішення для даного вводу.
Вхідні дані
Перша строка вводу містить кількість тестових випадків T. Опис тестових випадків слідує:
Перша строка кожного тестового випадку містить два цілі числа k та M, 1 ≤ k ≤ 4000, 3 ≤ M ≤ 10^9. Друга строка містить k розділених пробілом цілих чисел — значення p(1), p(2), ..., p(k) за модулем M.
Вихідні дані
Виведіть відповіді на тестові випадки в порядку їх появи у вводі. Для кожного тестового випадку виведіть один рядок, що містить одне ціле число: значення p(k+1) за модулем M.
Пояснення: перша послідовність просто 5^i mod 619, тому наступний елемент це 5^5 mod 619 = 30. Друга послідовність це 2 · 1^i + 3^i mod 101.