== 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)$

4902