tetris

Qwerty a inventat o nouă variantă a faimosului joc TETRIS. În varianta sa, jocul prezintă un şir de N boluri numerotate de la $1$ la $N$ care în momentul iniţial sunt goale. Qwerty vrea să facă $M$ operaţii pe acest şir de boluri. O operaţie constă în alegerea unui interval continuu de boluri $[A, B]$ şi adăugarea în fiecare bol din acest interval a unei bomboane de culoare $C$. De asemenea, dacă în orice moment de timp într-un anumit bol se află două bomboane de aceeaşi culoare $C$ ele dispar, iar dacă $C$ este mai mare decât $1$ atunci în locul acestora apare o bomboană de culoare $C-1$.

Operaţiile pe care le va face Qwerty sunt definite prin relaţie recurentă. El începe cu numerele $A_1 \ B_1 \ C_1$ şi pentru oricare $i$ mai mare decât $1$, utilizează apoi relaţiile:

• $A_i = Min(N, (A_{i-1} \cdot i) \ \% \ 1 \ 008 \ 989)$
• $B_i = Min(N, (B_{i-1} \cdot i) \ \% \ 1 \ 008 \ 989)$
• $C_i = (C_{i-1} \cdot X + Y)\ \%\ 47 + 1$

Qwerty va pune câte o bomboană de culoare $C_i$ în toate bolurile aflate între $Min(A_i,B_i)$ şi $Max(A_i,B_i)$.

Cerinţă

Deoarece Qwerty e mofturos din fire, doreşte ca înainte de a face operaţiile, să ştie care este numărul de bomboane care va ramane în boluri şi de aceea vă roagă să aflaţi acest număr pentru el.

Date de intrare

Pe prima linie a fişierului de intrare tetris.in se vor afla şapte numere naturale $N \ M \ A \ B \ C \ X \ Y$ având semnificaţiile din enunţ.

Date de ieșire

În fişierul de ieşire tetris.out veţi afişa un singur număr reprezentând numărul de bomboane ramase in boluri.

Restricții și precizări

• $5 \leq N,M \leq 400 \ 000$
• $1 \leq A, B \leq N$
• $1 \leq C \leq 47$
• $1 \leq X, Y \leq 100 \ 000$
• Modul de generare a datelor de intrare nu influenţează în nici un fel rezolvarea problemei!

Exemplu

tetris.in

5 5 2 4 30 2 10

tetris.out

8