prezenta

Prezenta

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

Poveste şi cerinţă...

Intr-o grupa sunt $N$ studenti, numerotati de la $1$ la $N$. Cand se face prezenta, aceastia se trec intr-o ordine oarecare pe foaia de prezenta de la ora respectiva.
 
In calculatorul din cabinetul profesorului exista un fisier cu numarul total de prezente ale studentilor. In acest fisier, studentii sunt trecuti in ordine, de la $1$ la $N$. La sfarsitul orei, profesorul se intoarce in cabinet si trece in fisier cate un punct pentru fiecare student prezent, in ordinea in care acestia apar pe foaia de prezenta.
 
Pentru a trece in fisier de la studentul $i$ la un student $j$ pentru care $j$ > $i$, profesorul inainteaza in fisier. Daca in schimb dupa studentul $i$ urmeaza pe foaia de prezenta un student $j$ astfel incat $j$ < $i$, profesorul trebuie sa faca o intoarcere in fisier (fiindca studentul $j$ apare in fisier inaintea studentului $i$). Profesorul uraste sa se intoarca in fisier.
 
Cand a trecut prezenta in calculator, profesorul s-a intors in fisier de $K$ ori. El se intreaba care este probabilitatea ca acest lucru sa se intample (sa se intoarca de $K$ ori). Fiindca studentii urasc probabilitatile, este suficient sa gaseasca in cate moduri se poate completa foaia de prezenta de catre cei $N$ studenti astfel incat profesorul sa realizeze $K$ intoarceri. Mai mult, este suficient sa afisati raspunsul modulo $10007$.
 

h2. Date de intrare

Fişierul de intrare $prezenta.in$ ...

Pe prima linie a fisierului $prezenta.in$ se gasesc numarul $T$ de teste. Pe fiecare din urmatoarele $T$ linii, se gaseste un test, dat prin cele doua numere naturale $N$ si $K$.

h2. Date de ieşire

În fişierul de ieşire $prezenta.out$ ...

Pe a $i$-a linie a fisierului $prezenta.out$ afisati raspunsul la testul al $i$-lea: in cate moduri se poate completa foaia de prezenta de catre cei $N$ studenti astfel incat profesorul sa faca $K$ intoarceri (modulo $10007$).

h2. Restricţii

* $... ≤ ... ≤ ...$

* 1 ≤ T ≤ 30
* 1 &le; $K$ < $N$ &le; 127

h2. Exemplu
table(example). |_. prezenta.in |_. prezenta.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 2
2 1
3 1
| 1
4

|

h3. Explicaţie
 
...

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

10453