== include(page="template/taskheader" task_id="prezenta") ==
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.
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.
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.
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.
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
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.
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
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).
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 ≤ k < n ≤ 127
* 1 ≤ T ≤ 30
* 1 ≤ $K$ < $N$ ≤ 127
h2. Exemplu
