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)