| Fişierul intrare/ieşire: | bacterii.in, bacterii.out | Sursă | Infoarena Monthly 2014, Runda 4 |
| Autor | Adrian Budau | Adăugată de |  Teodor Plop •Teodor94 |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Bacterii
Recent, cercetătorii institutului CDC 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.
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.
Date de intrare
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ţ.
Date de ieşire
Î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.
Restricţii
- 1 ≤ T ≤ 1.000
- 1 ≤ N ≤ 109
- 1 ≤ K ≤ 1018
- 3 ≤ M ≤ 109
- M este număr prim!
Exemplu
| bacterii.in | bacterii.out |
|---|---|
| 1 3 3 97 | 63 |
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.
