tetris3

Tetris3

== include(page="template/taskheader" task_id="tetris3") ==

Poveste şi cerinţă...

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~} * i) % 1008989)$
* $B{~i~} = Min(N, (B{~i-1~} * i) % 1008989)$
* $C{~i~} = (C{~i-1~}*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~})$.
 
h2. 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.

h2. Date de intrare

Fişierul de intrare $tetris3.in$ ...

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

h2. Date de ieşire

În fişierul de ieşire $tetris3.out$ ...

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

h2. Restricţii

* $... ≤ ... ≤ ...$

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

h2. Exemplu
table(example). |_. tetris3.in |_. tetris3.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|5 5 2 4 30 2 10
| 8

|

h3. Explicaţie
 
...
 

== include(page="template/taskfooter" task_id="tetris3") ==

4902