Kapitan Aydın və Dovşan-Adamın Tapmacası#6775

Kapitan Aydın və Dovşan-Adamın Tapmacası

1 saniyə

256 meqabayt

Asan

"Bu sənsən, Kapitan Aydındır!" – Dovşan-Adam qışqırdı – "sən bura mənim planlarımı pozmağa gəlmisən!"

"Bəli, bu mənəm." – Kapitan Aydın cavab verdi.

"Ama... haradan bildin ki, mən burada, 625-lə işarələnmiş gizli sığınacaqda olacam?! Sən mənim sirli kodumu qırdın?"

"Qırdım. Üç gün əvvəl, ipucların məni 5-ci yerə aparırdı, ertəsi gün 25-ə, dünən isə 125-ə — bunların hamısı 5-in qüvvətləridir. Keçən il isə eyni ardıcıllıq 13 ilə idi. Görünür, tapmacaların həmişə müəyyən ədədi ardıcıllıqlarla bağlı olur, Dovşan-Adam."

"Bu son deyil! Mən... arifmetikadan dərs alacam!" – Dovşan-Adam qışqırdı, onu aparanda – "Sən heç vaxt nə baş verəcəyini bilməyəcəksən... Ay! Qulaqlarım yox!"

"Ola bilər, amma indi səni yaxalayırlar." – Kapitan qürurla əlavə etdi.

Təəssüf ki, Dovşan-Adam həqiqətən biraz daha inkişaf etmiş arifmetikanı öyrənib. Bunu başa düşmək üçün aşağıdakı ardıcıllığı $F_{n}$ F_n müəyyən edək (Fibonacci ardıcıllığına bir o qədər də bənzəmir):

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

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

$F_{n} = F_{n - 1} + F_{n - 2}$ \mathbf{F_n = F_{n-1} + F_{n-2}} harada $n \geq 3.$

Dovşan-Adam bütün köhnə tapmaca ideyalarını yeni əzəmətli tapmacada birləşdirib. $i$ -ci gündə o, aşağıdakı kimi müəyyən olunan $p (i)$ nömrəli yerə işarə edir:

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

Buradakı $k$ və tam ədədi əmsallar $a_{1}, \dots, a_{k}$ a_1, \ldots, a_k sabitdir. Kapitan Aydın $k$ -nı tapıb, lakin əmsalları bilmir. Ona $p (1), p (2), \dots, p (k)$ p(1), p(2), \ldots, p(k) verilib, sizdən isə $p (k + 1)$ p(k+1)-i tapmaqda kömək etməyinizi istəyir. Böyük ədədlərdən qaçmaq üçün bütün hesablamaları verilmiş $M$ sadə ədədinə görə modulla aparın. Verilir ki, $F_{1}, F_{2}, \dots, F_{n}$ F_1, F_2, \ldots, F_n ardıcıllıqları $M$ modulunda cüt-cüt fərqlidirlər və verilmiş giriş üçün həmişə yeganə həll mövcuddur.

Giriş

Girişin birinci sətrində testlərin sayı $T$ verilir. Test təsvirləri aşağıdakı kimidir:

Hər bir testin birinci sətrində iki tam ədəd $k$ və $M$ verilir, $1 \leq k \leq 4000$ 1 \le k \le 4000, $3 \leq M \leq 1 0^{9}$ 3 \le M \le 10^9. İkinci sətirdə $k$ tam ədəd — $p (1), p (2), \dots, p (k)$ p(1), p(2), \ldots, p(k)-nin $M$ moduluna görə qiymətləri verilib.

Çıxış

Testlərə uyğun olaraq cavabları girişdəki ardıcıllıqla çap edin. Hər test üçün çıxışa bir sətirdə bir tam ədəd yazın: $p (k + 1)$ p(k+1)-in $M$ moduluna görə qiymətini.

İzah: birinci ardıcıllıq sadəcə $5^{i}$ 5^i $mod$ $619$ -dir, buna görə növbəti element $5^{5} mod 619 = 30$ 5^5\ \mod\ 619 = 30-dur. İkinci ardıcıllıq isə $2 \cdot 1^{i} + 3^{i} mod 101$ 2 \cdot 1^i + 3^i \mod 101 ardıcıllığıdır.

Nümunələr

Nümunə 1