| 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 ≤ 1018
- Pentru 8 puncte, Q ≤ 50, N ≤ 100
- Pentru alte 8 puncte, Q ≤ 2000, N ≤ 105
- Pentru alte 16 puncte, Q ≤ 2000, N ≤ 109
- Pentru alte 16 puncte, Q ≤ 2000, N ≤ 1018
- Pentru alte 16 puncte, Q ≤ 105, N ≤ 109
- Pentru alte 36 puncte, Q ≤ 105, N ≤ 1018
- Numărul de locuitori din orice cartier va fi par.
- Casele din fiecare cartier sunt aranjate în cerc.
Exemplu
| alee2.in | alee2.out |
|---|---|
| 3 2 4 10 | 1 2 42 |
