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

Bercea tocmai şi-a procurat (prin mijloace îndoielnice) $Q$ limuzine. Acum, pentru a arăta tuturor noile sale achiziţii, el s-a hotărât să facă mai multe plimbări prin oraş, oraşul fiind de fapt un graf *neorientat* cu $N$ noduri şi $M$ muchii. Un drum se defineşte ca fiind o secvenţă de noduri $a{~1~}$, $a{~2~}$, ..., $a{~k~}$ astfel încât să existe muchia ({$a{~i~}$}, $a{~i+1~}$), oricare ar fi $1$ ≤ $i$ ≤ $k-1$. Astfel orice nod poate fi folosit de oricâte ori într-un drum, la fel şi orice muchie. Lungimea unui drum este numărul de noduri care fac parte din drumul respectiv.
Totuşi Bercea nu doreşte să facă drumuri mai lungi de $K$ noduri, deoarece atunci ar putea ieşi din sfera sa de influenţă din oraş. Aşadar, fiind date $Q$ perechi de noduri $i$ si $ji$, aflaţi numărul de drumuri care încep în nodul $i$, se termină in nodul $ji$, iar lungimea fiecărui drum este ≤ $K$.

Bercea tocmai şi-a procurat (prin mijloace îndoielnice) o nouă limuzină. Acum, pentru a arăta tuturor noua sa achiziţie, el s-a hotărât să facă o plimbare prin oraş, oraşul fiind de fapt un graf *neorientat* cu $N$ noduri şi $M$ muchii. Un drum se defineşte ca fiind o secvenţă de noduri $a{~1~}$, $a{~2~}$, ..., $a{~k~}$ astfel încât să existe muchia ({$a{~i~}$}, $a{~i+1~}$), oricare ar fi $1$ ≤ $i$ ≤ $k-1$. Astfel orice nod poate fi folosit de oricâte ori într-un drum, la fel şi orice muchie. Lungimea unui drum este numărul de noduri care fac parte din drumul respectiv.
Totuşi Bercea nu doreşte să facă drumuri mai lungi de $K$ noduri, deoarece atunci ar putea ieşi din sfera sa de influenţă din oraş. Aşadar, fiind date două noduri $i$ si $ji$, aflaţi numărul de drumuri care încep în nodul $i$, se termină in nodul $ji$, iar lungimea fiecărui drum este ≤ $K$.

Deoarece numărul de drumuri poate fi foarte mare şi Bercea nu ştie să numere decât până la câte milioane de € are, afişaţi răspunsul modulo $10 007$.
h2. Date de intrare