== include(page="template/taskheader" task_id="invazie") ==
Poveste şi cerinţă...
Din cauza apropierii verii, Autoritatile Orasului, desi obosite dupa lupta cu zapada, din iarna abia apusa, se pregatesc de lupta cu tantarii. Pentru a face fata cu brio incercarii ce se apropie, trebuie ca mai intai sa calculeze numarul de tantari daunatori, care vor invada Orasul, in prima zi de vara.
Se stie ca exista doua tipuri de tantari: daunatori si inofensivi. De asemenea, se mai stie faptul ca in ziua 0 (azi), exista un singur tantar daunator, si niciun tantar inofensiv. In fiecare zi, fiecare tantar se transforma in K tantari de acelasi tip cu el si in P tantari de celalalt tip.
Stiind ca vara soseste peste exact N zile, Autoritatile va cer sa calculati numarul de tantari daunatori care vor invada Orasul in prima zi de vara. Intrucat acest numar poate fi foarte mare, salvarea Orasului va putea fi realizata si daca se cunoaste doar numarul cerut modulo 666013.
h2. Date de intrare
Fişierul de intrare $invazie.in$ ...
Fişierul de intrare $invazie.in$ contine pe prima linie numarul T de teste. Pe urmatoarele T linii se gasesc cate trei numere in ordinea K P N, avand semnificatia din enunt.
h2. Date de ieşire
În fişierul de ieşire $invazie.out$ ...
În fişierul de ieşire $invazie.out$ veti afisa T linii, pe fiecare linie aflandu-se rezultatul cerut pentru testul corespunzator din fisierul de intrare.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ T ≤ 100.000.$
* $0 ≤ K, P ≤ 2 000 000 000.$
* $0 ≤ N ≤ 10^18.$
* $Pentru 20% din teste, T ≤ 100 si N ≤ 1000.$
h2. Exemplu
table(example). |_. invazie.in |_. invazie.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 3
1 2 5
3 4 0
2 2 2
| 121
1
8
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="invazie") ==
== include(page="template/taskfooter" task_id="invazie") ==
