| Fişierul intrare/ieşire: | invazie.in, invazie.out | Sursă | FMI No Stress 2012 |
| Autor | Florian Marcu | Adăugată de |  Florian Marcu •Florian |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 5120 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Invazie
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.
Date de intrare
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.
Date de ieşire
Î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.
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.
Exemplu
| invazie.in | invazie.out |
|---|---|
| 3 1 2 5 3 4 0 2 2 2 | 121 1 8 |
