Revizia anterioară Revizia următoare
Fişierul intrare/ieşire: | Invalid task id .in, Invalid task id .out | Sursă | Invalid task id |
Autor | Invalid task id | Adăugată de | Invalid task id |
Timp execuţie pe test | Invalid task id sec | Limită de memorie | Invalid task id kbytes |
Scorul tău | Invalid task id | Dificultate | Invalid task id |
Vezi solutiile trimise | Statistici
Invalid task id
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 numÄ?rul 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 ≤ 20000
- 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 |