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 A1 B1 C1 şi pentru oricare i mai mare decât 1, utilizează apoi relaţiile: Ai = Min(N, (Ai-1 * i) % 1008989) Bi = Min(N, (Bi-1 * i) % 1008989) Ci = (Ci-1*X + Y) % 47 + 1
Qwerty va pune câte o bomboană de culoare Ci în toate bolurile aflate între Min(Ai,Bi) şi Max(Ai,Bi).
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 tetris1.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 tetris1.out veţi afişa un singur număr reprezentând numărul bomboane ramase în boluri.
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!