Enunț
Ana Mia are o recurență liniară de forma P[N] = A[1]*P[N-1] + A[2]*P[N-2] + A[3]*P[N-3] + A[4]*P[N-4]
, N ≥ 5
. Studiind-o, îi vine o idee MAXIMĂ de problemă: “Pentru câte cvadriplete (P[1], P[2], P[3], P[4])
din mulțimea numerelor naturale [1, B]
valoarea P[N]
modulo K
are valoarea X
?”
Cerința
Scrieți un program care citind N
, B
, X
, K
, și numerele A[i], 1 ≤ i ≤ 4
rezolvă problema Anei.
Date de intrare
Fișierul de intrare recc.in
conține pe prima linie numerele N
, B
, X
, K
, separate printr-un spațiu, iar pe a doua linie 4
numere naturale separate prin spații, reprezentând numerele A[i], 1 ≤ i ≤ 4
.
Date de ieșire
Fișierul de ieșire recc.out
va conține pe prima linie numărul ANS
, răspunsul problemei puse de Ana Mia.
Restricții și precizări
5 ≤ N ≤ 10^18
1 ≤ B ≤ 1000
1 ≤ K ≤ 10^9
0 ≤ X < K
- numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât
1.000.000.000
Exemplu:
recc.in
6 2 3 4 1 2 3 1
recc.out
2
Explicație
Soluțiile sunt (2, 1, 2, 1)
și (2, 2, 2, 1)