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, da nastere la K tantari de acelasi tip cu el si la P tantari de celalalt tip.

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. Restricţii

* $1 ≤ T ≤ 100.000$
* $0 ≤ N ≤ 10^18$
* $1 ≤ T ≤ 100.000$

* $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

7945