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

Î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**.
 

Poveste şi cerinţă...

h2. Date de intrare

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.

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

h2. Date de ieşire

Î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**.

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

h2. Restricţii

* $1 ≤ Q ≤ 10.000$
* $1 ≤ N ≤ 10^18^$
* Aici o sa pun restrictiile pentru punctaje!!!!
* Pentru $20$ de puncte, $N &le; 5, M = 11, A{~i~} < 2^3^$
* Pentru alte $20$ de puncte, $N &le; 100, M = 997, A{~i~} &le; 2^5^$
* Pentru alte $20$ de puncte, $M = 10^9^+7$
* Pentru alte $20$ de puncte, $N &le; 1.000, M &le; 10^3^, A{~i~} < 2^30^$
* 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 |

| 3
2
4
10
| 2
5
42
|
 

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

h3. Explicaţie

* O sa vedem daca va fi cazul.
 

...

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