Fişierul intrare/ieşire:	alee2.in, alee2.out	Sursă	inspirată din FPC 2021
Autor	Cristian-Alexandru Botocan	Adăugată de	Botocan Cristian-Alexandru •Botzki17
Timp execuţie pe test	0.1 sec	Limită de memorie	500000 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Alee în cartier

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

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.

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.

Restricţii

• 1 ≤ Q ≤ 10.000
• 2 ≤ N ≤ 10¹⁸
• Pentru 8 puncte, Q ≤ 50, N ≤ 100
• Pentru alte 8 puncte, Q ≤ 2000, N ≤ 10⁵
• Pentru alte 16 puncte, Q ≤ 2000, N ≤ 10⁹
• Pentru alte 16 puncte, Q ≤ 2000, N ≤ 10¹⁸
• Pentru alte 16 puncte, Q ≤ 10⁵, N ≤ 10⁹
• Pentru alte 36 puncte, Q ≤ 10⁵, N ≤ 10¹⁸
• Numărul de locuitori din orice cartier va fi par.
• Casele din fiecare cartier sunt aranjate în cerc.

Exemplu

Explicaţie

• O sa vedem daca va fi cazul.

Cum se trimit solutii?