== include(page="template/taskheader" task_id="bacterii") ==
Poveste şi cerinţă...
Recent, cercetătorii institutului 'CDC':http://en.wikipedia.org/wiki/Centers_for_Disease_Control au început să studieze amănunţit procesul de multiplicare al bacteriilor Streptococcus paracetivorus. Aceştia au observat o anomalie şi anume, din $N$ bacterii iniţiale, după un pas de multiplicare, acestea devin $N * (N - 3) + N + 2$ bacterii. Pentru a preveni o creştere rapidă a acestui tip de bacterii, cercetătorii au nevoie să ştie câte bacterii vor exista după $K$ paşi de multiplicare, modulo $M$, unde $M$ este număr prim.
h2. Cerinţă
Se dă $T$, numărul de teste, iar pentru fiecare test $3$ numere naturale $N$, $K$ şi $M$. Să se spună câte bacterii vor exista după $K$ paşi de multiplicare ştiind că iniţial existau $N$ bacterii. Pentru fiecare test, rezultatul cerut se va afişa modulo $M$.
h2. Date de intrare
Fişierul de intrare $bacterii.in$ ...
Fişierul de intrare $bacterii.in$ conţine pe prima linie numărul de teste, $T$. Pe următoarele $T$ linii, pentru fiecare test, se găsesc $3$ numere naturale $N$, $K$ şi $M$, având semnificaţia din enunţ.
h2. Date de ieşire
În fişierul de ieşire $bacterii.out$ ...
În fişierul de ieşire $bacterii.out$ se vor găsi $T$ linie, iar fiecare linie $i$ va conţine un singur număr natural, reprezentând rezultatul dorit pentru testul $i$.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ T ≤ 1.000$
* $1 ≤ N ≤ 10^9^$
* $1 ≤ K ≤ 10^18^$
* $3 ≤ M ≤ 10^9^$
* $M este număr prim!$
h2. Exemplu
table(example). |_. bacterii.in |_. bacterii.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 1
3 3 97
| 63
|
h3. Explicaţie
...
După primul pas, numărul de bacterii devine 3 * 0 + 3 + 2, şi anume 5.
După al doilea pas, numărul de bacterii devine 5 * 2 + 5 + 2, şi anume 17.
După al treilea pas, numărul de bacterii devine 17 * 14 + 17 + 2, şi anume 257.
257 % 97 = 63.
== include(page="template/taskfooter" task_id="bacterii") ==
