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

== include(page="template/taskheader" task_id="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.
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.

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