tetris3

Tetris3

== include(page="template/taskheader" task_id="tetris3") ==
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)$

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. Cerinta

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.

* $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!

* *Modul de generare a datelor de intrare nu influenţează în nici un fel rezolvarea problemei!*

h2. Exemplu

4902