== include(page="template/taskheader" task_id="ciuperci") ==

Poveste şi cerinţă...

 
Un arbore este super-echilibrat daca are urmatoarele proprietati:
       ●	este binar, deci fiecare nod are maxim $2$ fii.
       ●	pentru fiecare nod, modulul diferentei intre numarul de noduri ale subarborelui stang si numarul de noduri ale subarborelui drept sa fie maxim $1$.
 
Se dau $Q$ intrebari de tipul “Cati arbori super-echilibrati cu $N$ noduri exista?”. Deoarece numarul acestora poate ajunge destul de mare rezultatul se va calcula modulo $666013$.

h2. Date de intrare

Fişierul de intrare $ciuperci.in$ ...

Fişierul de intrare $ciuperci.in$ contine pe prima linie $Q$, numarul de intrebari. Urmeaza $Q$ linii. Pe linia $i+1$ se afla un numar $N{~i~}$ care reprezinta numarul de noduri pentru intrebarea $i$.

h2. Date de ieşire

În fişierul de ieşire $ciuperci.out$ ...

În fişierul de ieşire $ciuperci.out$ contine $Q$ numere, cate unul pe linie. Numarul de pe linia $i$ reprezinta raspunsul la intrebarea $i$.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ Q ≤ 10^5^$
* $1 ≤ N{~i~} ≤ 10^16^$
* $a$ modulo $b$ reprezinta restul impartirii lui $a$ la $b$
* doi arbori sunt consideranti diferiti daca parcurgerea lor in inordine este diferita
* parcurgerea in inordine este parcurgerea dupa ordinea Fiu_stanga, Radacina, Fiu_dreapta
* $Atentie!$ Se recomanda folosirea tipului $long long$ pentru cei care implementeaza in $C/C++$ si $int64$ pentru cei care implementeaza in $Pascal$

h2. Exemplu
table(example). |_. ciuperci.in |_. ciuperci.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 4
1
2
4
5
| 1
2
4
4

|
h3. Explicaţie

...

Pentru $1$ avem doar radacina.
 
Pentru $2$ avem radacina cu un fiu stang sau unul drept, deci $2$ solutii.
 

== include(page="template/taskfooter" task_id="ciuperci") ==

6377