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

Poveste şi cerinţă...

În oraşul Andrei, oamenii vor să socializeze cât mai mult posibil după pandemie. Având în vedere că au cheltuit bani doar pe alimente în timpul pandemiei, s-au gândit că a avea resurse nelimitate ar crea alei. O alee este o legătură între 2 case **distincte** şi toate casele trebuie să aibă o alee conectată la o casă din **acelaşi** cartier. Practic, locuitorii unui cartier vor să afle în câte moduri pot fi construite alei între 2 perechi diferite, astfel încât aleile să nu se intersecteze (fiecare casă este conectată cu o alee).
 
 
Având în vedere că oraşul Andrei are $Q$ cartiere, calculaţi pentru fiecare cartier cu $N$ număr de case câte astfel de alei pot fi construite de ţara locuitorilor? Deoarece acest număr poate fi foarte mare, răspunsul ar trebui să fie **modulo 313109**.
 

h2. Date de intrare

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

Fişierul de intrare $alee2.in$ contine, pe prima linie, un singur număr natural $Q$. Pe urmatoarele $Q$ linii se afla un numar par $N$, reprezentând numărul de casele din cartier.

h2. Date de ieşire

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

În fişierul de ieşire $alee2.out$ se vor afla $Q$ linii, fiecare linie conţinând un număr- numărul de modalităţi posibile în care aleile poate fi construite în fiecare cartier. Acest număr trebuie să fie **modulo 313109**.

h2. Restricţii

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

* $1 ≤ Q ≤ 10.000$
* $2 ≤ N ≤ 10^18^$
* Pentru $8$ puncte, $Q ≤ 50, N ≤ 100$
* Pentru alte $8$ puncte, $Q ≤ 2000, N ≤ 10^5^$
* Pentru alte $16$ puncte, $Q ≤ 2000, N ≤ 10^9^$
* Pentru alte $16$ puncte, $Q ≤ 2000, N ≤ 10^18^$
* Pentru alte $16$ puncte, $Q ≤ 10^5^, N ≤ 10^9^$
* Pentru alte $36$ puncte, $Q ≤ 10^5^, N ≤ 10^18^$
* Numărul de locuitori din orice cartier va fi **par**.
* Casele din fiecare cartier sunt aranjate în cerc.
 

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

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

| 3
2
4
10
| 1
2
42
|

h3. Explicaţie
...

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