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

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 - 2) + 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$.

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ţă

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

9811