tombola

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 $S_1$, $S_2$, $\dots$, $S_N$. Programul respectiv primeşte patru numere naturale $A$, $B$, $C$, $D$ și primul număr din șir $S_1$ . Al $i$-lea număr generat se obține după regula $S_i$ = (($S_{i-1} \% A$) $\cdot \ B + C$) $\% D$, unde $1 < i \leq N$ iar $a$ % $b$ reprezintă restul împărțirii lui $a$ la $b$ ($b \neq 0$)

Cerință

Cunoscându-se numerele naturale $N$, $S_1$, $A$, $B$, $C$, $D$, scrieți un program care rezolvă următoarele cerințe:

1. pentru fiecare dintre termenii șirului $S_1$, $S_2$, $\dots$, $S_N$, 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 $10^{18}$ + $31$;
2. pentru fiecare dintre termenii șirului $S_1$, $S_2$, $\dots$, $S_N$, 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 $10^{18}$ + $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$, $S_1$, $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 \leq N \leq 500 \ 000$
• $1 < S_1, C, D \leq 10^{17}$
• $1 < A, B \leq 10^9$
• Se garantează că $S_i$ > $1$, oricare $1 \leq i \leq N$
• Pentru teste valorând $50$ de puncte cerința este $1$
• Pentru $30$% din numărul total de teste, $N \cdot D \leq 10^6$ și $N \cdot S_1 \leq 10^6$ ($50$% dintre acestea fiind pentru cerinţa $1$)
• Pentru $60$% din numărul total de teste, $N \leq 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 $S_1 = 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 $S_1 = 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