Fişierul intrare/ieşire:invazie.in, invazie.outSursăFMI No Stress 2012
AutorFlorian MarcuAdăugată deFlorianFlorian Marcu Florian
Timp execuţie pe test1 secLimită de memorie5120 kbytes
Scorul tăuN/ADificultateN/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.ininvazie.out
3
1 2 5
3 4 0
2 2 2
121
1
8
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content