== include(page="template/taskheader" task_id="Doipe") ==

Poveste si cerinta...

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.

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

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

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

h2. Exemplu

table(example). |_. Doipe.in |_. Doipe.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

table(example). |_. doipe.in |_. doipe.out |
| 3
2
<
10
<><<<><<<
15
<<>>><><>>><><>
| 1
2896
17401

|

h3. Explicatie
 
...
 

== include(page="template/taskfooter" task_id="Doipe") ==