Aflat într-o vizită cu părinții, Iliuță primește un bilet la tombolă pe care este scris un număr natural S. Pentru a câștiga un premiu, Iliuță trebuie să afle, plecând de la numărul S, un număr câștigător X. Pentru a-l ajuta să ghicească numărul câștigător, mama îi spune lui Iliuță că numărul S de pe biletul său este suma dintre numărul câștigător X și toate numerele obținute plecând de la numărul câștigător X, prin ștergerea cifrei unităților numărului X, apoi, succesiv, prin ștergerea cifrei unităților numărului obținut la pasul anterior, până se ajunge la un număr de o singură cifră.
De exemplu, dacă numărul X este 2019, atunci din X se pot obține după regula de mai sus trei numere: 201, 20 și 2. Suma tuturor acestor numere este S = 2019 + 201 + 20 + 2 = 2242. Deci, dacă pe biletul lui Iliuță se află numărul S=2242, atunci numărul câștigător corespunzător lui S este X = 2019.
Din păcate, nu toate numerele naturale permit determinarea unui număr câștigător. De exemplu, pentru numărul 21 nu există niciun număr natural X din care să putem obține 21 după regula descrisă de mama lui Iliuță.
Cu ajutorul unui program a fost generat automat un șir de N numere, numerotate în ordinea generării S1, S2, …, SN. Programul respectiv primește patru numere naturale A, B, C, D și primul număr din șir S1. Al i-lea număr generat se obține după regula
Si =((Si-1 % A) * B + C) % D,
unde 1 < i ≤ N, iar a % b reprezintă restul împărțirii lui a la b (b ≠ 0).

Cerința

Cunoscându-se numerele naturale N, S1, A, B, C, D, scrieți un program care rezolvă următoarele cerințe:
1) pentru fiecare dintre termenii șirului S1, S2, …, SN, determină cel mai mare număr natural mai mic strict decât termenul respectiv, pentru care există un număr câștigător; programul va afișa restul împărțirii sumei numerelor obținute la 1018+31;
2) pentru fiecare dintre termenii șirului S1, S2, …, SN, determină câte numere naturale mai mici sau egale cu termenul respectiv NU au număr câștigător; programul va afișa restul împărțirii sumei rezultatelor obținute la 1018+31.

Date de intrare

Fișierul de intrare tombola.in conține pe prima linie numărul natural p, reprezentând cerința care trebuie rezolvată (1 sau 2). Pe a doua linie se află, în această ordine, numerele naturale N S1 A B C D, separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire tombola.out va conține un singur număr natural care reprezintă rezultatul la cerința p.

Restricții și precizări

• 1 ≤ N ≤ 500.000
• 1 < S1, C, D ≤ 1017
• 1 < A, B ≤ 109
• Se garantează că Si > 1, oricare 1 ≤ i ≤ N
• Pentru teste valorând 50 de puncte cerința este 1.
• Pentru 30% din numărul total de teste, N * D ≤ 106 și N * S1 ≤ 106 (50% dintre acestea fiind pentru cerința 1)
• Pentru 60% din numărul total de teste, N ≤ 30.000 (50% dintre acestea fiind pentru cerința 1).

Exemplul 1:

tombola.in

1
1 22 3 3 3 3

tombola.out

20

Explicație

Se rezolvă cerința 1. Avem un singur termen în șir S1 = 22. Numărul 20 este cel mai mare număr strict mai mic decât 22 care acceptă un număr câștigător (X = 19 deoarece 20 = 19 + 1).

Exemplul 2:

tombola.in

2
1 22 3 3 3 3

tombola.out

2

Explicație

Se rezolvă cerința 2. Avem un singur termen în șir S1=22. Există două numere mai mici sau egale cu 22 care NU acceptă număr câștigător, 10 și respectiv 21.

Exemplul 3:

tombola.in

1
3 12345678901234567 999999999 123456789 98765432109876543 1020304050607080

tombola.out

12805467424792840

Exemplul 4:

tombola.in

2
3 98765432109876543 999999999 123456789 12345678901234567 1020304050607080

tombola.out

9912065223185559