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

Amatias e cel mai puternic super erou; intr-adevar, e destul de puternic sa bata oricare adversar intr-o singura lovitura de picior! Pe de alta parte, celelalte federatii de eroi din restul pamantului sunt mai putin puternice. Sunt $T$ federatii. Federatia $i$ se caracterizeaza prin $5$ numere diferite: $x[~i~], y[~i~], a[~i~], b[~i~], m[~i~]$. Puterea $p[~i~]$ a federatiei se defineste prin ecuatia <tex> p_i = \sum_{j = a_i}^{b_i} x_i^{y_i^j} \mod m_i </tex>. Pentru a ne da seama cu cat mai puternic este Amatias fata de diversele federatii, dandu-se $x[~i~], y[~i~], a[~i~], b[~i~], m[~i~]$, sa se gaseasca valoarea lui $p[~i~]$.

Poveste şi cerinţă...

h2. Date de intrare

Fişierul de intrare $powerful.in$ va contine pe primul rand $T$.
Pe urmatoarele $T$ randuri va aparea, pe randul $i+1$, numerele $x[~i~], y[~i~], a[~i~], b[~i~], m[~i~]$.

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

h2. Date de ieşire

În fişierul de ieşire $powerful.out$ afisati $T$ randuri: valorile lui $p[~i~]$ pentru $i = 1, ..., T$.

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

h2. Restricţii

* $1 ≤ T ≤ 100$
* $1 ≤ x[~i~], y[~i~], a[~i~], b[~i~] ≤ 10^18^$
* $1 ≤ m[~i~] ≤ 10.000$
* $m[~i~]$ este prim.

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

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

| 6
1 3 2 5 31
5 1 7 20 37
6 7 8 9 7
6 7 8 9 7919
6 7 8 9 1621
123 543 23 567 3163
| 4
33
5
3268
634
2608

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

|
h3. Explicaţie