nkl

Nkl

h2. Date de ieşire

Fişierul $nkl.out$ conţine $Q$ linii, corespunzătoare celor $Q$ perechi de numere $K$ şi $L$. Pentru fiecare pereche se va afişa numărul secvenţelor ordonate de dimensiune $K$ care sunt $L-perfecte$ modulo $1000000007$.

Fişierul $nkl.out$ conţine $Q$ linii, corespunzătoare celor $Q$ perechi de numere $K$ şi $L$. Pentru fiecare pereche se va afişa numărul secvenţelor ordonate de dimensiune $K$ care sunt $L-perfecte$ modulo $10^9^ + 7$.

h2. Restricţii

* $1 <= N <= 1 000 000 000$.

* $1 <= N <= 10^9^$.

* $1 <= K, L, Q <= 1000$.
* $L < K$.
* Pentru unele teste în valoare de $5$ puncte $K=3$.
* Pentru alt teste în valoare de $5$ puncte $L=2$.
* Problema va fi evaluată pe teste în valoare de $90$ de puncte.

* Exemplul va reprezenta teste în valoare de $10$ puncte "din oficiu".

* Exemplele vor reprezenta teste în valoare de $10$ puncte "din oficiu".

h2. Exemplu