| Fişierul intrare/ieşire: | doipe.in, doipe.out | Sursă | Winter Challange, Runda 01, clasele 11-12 |
| Autor | Bogdan Ionescu, Csaba Patcas, Mugurel Ionut Andreica | Adăugată de |  Bogdan-Alexandru Stoica •fireatmyself |
| Timp execuţie pe test | 0.3 sec | Limită de memorie | 11096 kbytes |
| Scorul tău | N/A | Dificultate |   3/5 |
Vezi solutiile trimise | Statistici
Doipe
Pentru orice permutare de N elemente putem determina un sir de N-1 relatii (relatiile folosite fiind < sau >). Daca al i-lea element al permutarii este mai mic decat al i+1-lea element, al i-lea element al sirului de relatii va fi <, in caz contrar, al i-lea element al sirului de relatii va fi >. De exemplu pentru permutarea (1,3,2,4) de patru elemente determinam sirul (<, >, <). Va trebui sa determinati cate permutari de N elemente exista carora le corespunde un anumit sir de relatii. Ne intereseaza doar restul impartirii acestui numar la 29997.
Date de intrare
Pe prima linie a fisierului doipe.in se va afla numarul T semnificand numarul testelor din fisier. Pe urmatoarele 2*T linii se vor afla informatii despre fiecare test. Astfel pe linia 2*k (1 ≤ k ≤ T) se va alfa numarul N, iar pe linia 2*k+1 (1 ≤ k ≤ T), sirul de relatii.
Date de iesire
Fisierul doipe.out va trebui sa contina exact T linii. Pe a i-a linie va trebui sa se afle raspunsul pentru al i-lea test din fisierul de intrare.
Restrictii
- 1 ≤ T ≤ 20
- 1 ≤ N ≤ 2.000
- 40% din fisierele de test vor avea toate valorile lui N mai mici sau egale cu 16
- 70% din fisierele de test vor avea toate valorile lui N mai mici sau egale cu 200
Exemplu
| doipe.in | doipe.out |
|---|---|
| 3 2 < 10 <><<<><<< 15 <<>>><><>>><>< | 1 2896 17401 |
