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

Deoarece numărul de drumuri poate fi foarte mare şi Bercea nu ştie să numere mai departe de câţi bani cash are, afişaţi răspunsul modulo $1 000 000 007$.

h2. Date de intrare