sir

Enunţ

Construim un şir recurent astfel:
$T_n = a \times {T_{n - 2}}^2 + b \times {T_{n - 1}}^2 + x \times T_{n - 2} + y \times T_{n - 1} + z$

Cerință

Fiind date $T_0, T_1, a, b, x, y, z$ şi $n$ calculaţi $T_n \ modulo$ un număr natural $M$.

Date de intrare

Fişierul de intrare sir.in conţine pe prima linie numerele naturale $T_0, T_1, a, b, x, y, z, M$ şi $n$ , separate prin
spaţiu, cu semnificaţia din enunţ.

Date de ieșire

Fişierul de ieşire sir.out va contine o singură linie pe care va fi scris un număr natural reprezentând $T_n \ modulo \ M$

Restricții și precizări

• $0 \leq a, b, c, y, z \leq 1 \ 000$;
• $0 \leq T_0, T_1 \leq 1 \ 000 \ 000 \ 000$;
• $0 \leq n \leq 10^{16}$;
• $0 < M \leq 7 \ 000$;

Exemplul

sir.in

1 1 0 0 1 1 0 1000 7

sir.out

21

Explicație

Termenii şirului sunt:

$T_0 = 1$
$T_1 = 1$
$T2 = 0 \times 1^2 + 0 \times 1^2 + 1 \times 1 + 1 \times 1 + 0 = 2$
$T3 = 0 \times 1^2 + 0 \times 2^2 + 1 \times 1 + 1 \times 2 + 0 = 3$
$T_4 = 0 \times 2^2 + 0 \times 3^2 + 1 \times 2 + 1 \times 3 + 0 = 5$
$T_5 = 0 \times 3^2 + 0 \times 5^2 + 1 \times 3 + 1 \times 5 + 0 = 8$
$T_6 = 0 \times 5^2 + 0 \times 8^2 + 1 \times 5 + 1 \times 8 + 0 = 13$
$T_7 = 0 \times 8^2 + 0 \times 13^2 + 1 \times 8 + 1 \times 13 + 0 = 21$
Rezultatul este $T_7 \ mod \ 1 \ 000 = 21$.