Fișierul intrare/ieșire	clasa0.in, clasa0.out	Sursă	ad-hoc
Autor	autor necunoscut	Adăugată de	Cristian Frâncu • francu
Timp de execuție pe test	0.2 sec	Limită de memorie	65536 KB
Scorul tău	N/A	Dificultate	2.5

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Clasa0

Astăzi este prima zi de școală pentru foarte mulți pre școlari. Doamna învățătoare Cristina decide să își facă grupe de elevi după gradul de colegiabilitate. Gradul de sociabilitate al unui grup este diferența maximă dintre gradul de colegiabilitate a doi elevi. Dacă în grup este doar un elev socializarea este 0.

Cerință

Doamna învățătoare vrea să știe care este suma maximă a socializării grupurilor. Voi trebuie să o ajutați!

Gradele de colegialitate se dau ca o secvență de numere A = a₁, a₂, ..., a_n astfel încît:

• a_i = (p * a_i-1 + q * a_i-2) % r, pentru orice i ≥ 3.

Date de intrare

Pe prima linie a fisierului de intrare clasa0.in se va găsi N, numărul elevilor (lungimea secvenței A). Pe cea de-a doua linie se vor găsi numerele a₁, a₂, p, q și r, numere ce determină unic secvența A.

Date de ieșire

În fișierul de ieșire clasa0.out trebuie să se afle valoarea dorită de doamna profesoară.

Restricții

• 2 ≤ N ≤ 10 milioane
• 0 ≤ a₁, a₂, r ≤ 2 miliarde
• -1 miliard ≤ p, q ≤ 1 miliard
• se garantează că toate elementele secvenței A sînt non-negative

Exemplu