Fişierul intrare/ieşire:	rsir.in, rsir.out	Sursă	Lot Alba 2007
Autor	Adrian Diaconu	Adăugată de	Adrian Diaconu •DITzoneC
Timp execuţie pe test	1 sec	Limită de memorie	6144 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Rsir

Construim un sir recurent astfel:

T_n = a * T_n-2² + b * T_n-1² + x * T_n-2 + y * T_n-1 + z

Cerinta

Fiind date T₀, T₁, a, b, x, y, z si n calculati T_n modulo un numar natural M.

Date de intrare

Fisierul de intrare rsir.in contine pe prima linie numerele naturale T₀, T₁, a, b, x, y, z, M si n, separate prin spatiu, cu semnificatia din enunt.

Date de iesire

Fisierul de iesire rsir.out va contine o singura linie pe care va fi scris un numar natural reprezentand T_n modulo M.

Restrictii

• 0 ≤ a, b, x, y, z ≤ 1.000
• 0 ≤ T₀, T₁ ≤ 1.000.000.000
• 0 ≤ n ≤ 10¹⁶
• 1 ≤ M ≤ 7.000

Exemplu

Explicatie

Termenii sirului sunt:
T₀=1
T₁=1
T₂=0*1²+0*1²+1*1+1*1+0=2
T₃=0*1²+0*2²+1*1+1*2+0=3
T₄=0*2²+0*3²+1*2+1*3+0=5
T₅=0*3²+0*5²+1*3+1*5+0=8
T₆=0*5²+0*8²+1*5+1*8+0=13
T₇=0*8²+0*13²+1*8+1*13+0=21
Rezultatul este T₇ mod 1000 = 21.

Cum se trimit solutii?