Revizia anterioară Revizia următoare
| 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 ≤ 2000
- 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 2000
Exemplu
| doipe.in | doipe.out |
|---|---|
| 3 2 < 10 <><<<><<< 15 <<>>><><>>><><> | 1 2896 17401 |
