pscfft

După îndelungi căutări, Ruffi a găsit manuscrisul adevărului, pe care erau scrise secretele antice ale FFT-ului. Cu ajutorul acestora a compus următoarea problemă:

Notăm cu ++ concatenarea a două șiruri (ex. [1, 2, 3] ++ [4, 5, 6] = [1, 2, 3, 4, 5, 6]).

Definim funcția inc în felul următor:
$inc([a_0, \dots, a_{n-1}], k, s) = [(a_0+k) \% s, \dots, (a_{n-1}+k) \% s]$, unde prin a%b s-a notat restul împărțirii lui a la b.

Definim recursiv familia de șiruri FFT în felul următor:
FFT(0, s) = [0]
FFT(k+1, s) = inc(FFT(k, s), 0, s) ++ inc(FFT(k, s), 1, s) ++ … ++ inc(FFT(k, s), s-1, s)

De exemplu:
FFT(1, 3) = [0, 1, 2],
FFT(2, 3) = [0, 1, 2, 1, 2, 0, 2, 0, 1],
FFT(3, 3) = [0, 1, 2, 1, 2, 0, 2, 0, 1, 1, 2, 0, 2, 0, 1, 0, 1, 2, 2, 0, 1, 0, 1, 2, 1, 2, 0]

Cerinţă

Dându-se un șir v de lungime N, un număr natural nenul s, se cere să se afle prima poziție unde se găsește v ca subsecvență în $FFT(10^{10^{10^{100}}}+ 1, s)$ și să se afișeze restul împărțirii acesteia la $10^9+7$, sau să se precizeze că nu apare în șir.

Date de intrare

Pe primul rând al fișierului de intrare pscfft.in apare numărul natural nenul T care reprezintă numărul de teste. Urmează T teste, fiecare cu următorul format:
Pe primul rând al unui test va apărea un număr natural nenul N, și un număr natural nenul s. Pe următoarea linie vor apărea câte N numere naturale între 0 și s-1, ce reprezintă valorile lui v.

Date de ieşire

În fișierul de ieșire pscfft.out pentru fiecare test se va afișa pe câte o linie fie restul împărțirii la $10^9+7$ a poziției de început a primei apariții a șirului v ca subsecvență în șirul $FFT(10^{10^{10^{100}}}+ 1, s)$ , sau -1 dacă aceasta nu există.

Restricţii și precizări

• 1 ≤ s ≤ 1 000 000 000
• 1 ≤ N ≤ 500 000
• 1 ≤ T ≤ 500 000
• Suma N-urilor pentru toate testele dintr-un fișier nu depășeste 500 000.
• Pentru 10% din punctaj, T ≤ 20 , N ≤ 100 și s ≤ 3
• Pentru alte 10% din punctaj, avem T ≤ 20 , s ≤ 4 și răspunsul, dacă există, nu depășește 500 000
• Pentru alte 10% din punctaj, s ≤ 4
• Pentru alte 30% din punctaj, s ≤ 5
• Pentru alte 30% din punctaj, s ≤ N
• Se garantează că dacă pentru un test există un K astfel încât șirul v să apară în șirul FFT(K, s) atunci acest șir v va apărea și în șirul $FFT(10^{10^{10^{100}}}+ 1, s)$

Exemple

pscfft.in

5
4 2
1 0 1 1
5 3
2 0 1 2 1
20 6
2 4 5 0 1 2 3 5 0 1 2 3 4 0 1 2 3 4 5 1
2 10000000
5 5
5 5
4 3 2 1 0

pscfft.out

11
134
83
273492549
-1

Sunt T=5 teste

În primul test primele 16 numere din $FFT(10^{10^{10^{100}}}+ 1, s)$ sunt 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0

Ultimul test nu are soluție.