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

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

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$ ≤ $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$
 

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") ==

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

1541