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

În pădurea cu alune, aveau o cabană $N$ pitici. În cabană sunt exact $K$ camere în care se poate dormi. Cum somnul nu este deloc de neglijat în lumea piticilor, aceştia se joacă înainte de culcare astfel: Piticii intră pe rând în cabană, începând cu piticul $1$, până la piticul $N$ şi se duc în camera în care vor dormi. Un pitic îşi alege camera în care va dormi în felul următor:

În pădurea cu alune, aveau o cabană $N$ pitici. În cabană sunt exact $K$ camere în care se poate dormi. Cum somnul nu este deloc de neglijat în lumea piticilor, aceştia se joacă înainte de culcare astfel: Piticii intră pe rând în cabană, începând cu piticul $1$, până la piticul $N$, şi se duc în camera în care vor dormi. Un pitic îşi alege camera în care va dormi în felul următor:

* Se duce în camera care a fost aleasă de cât mai puţini pitici.
* Dacă sunt mai multe camere cu această proprietate, piticul va alege oricare dintre acestea.
Când ajunge Albă ca Zăpada în cabană, aceasta se întreabă:

* Oare în câte moduri poate fi ocupată cabana de către cei $N$ pitici?

* Oare în câte moduri poate fi ocupată cabana de cei $N$ pitici?

Două moduri de ocupare a cabanei sunt considerate distincte dacă cel puţin o cameră conţine alţi pitici. Pentru ca Albă ca Zăpada este o prinţesă de treabă, aceasta vă cere răspunsul *modulo $1000000007$*.

Două moduri de ocupare a cabanei sunt considerate distincte dacă există cel puţin un pitic care să se afle într-o cameră distinctă.

h2. Date de intrare

h2. Restricţii

* $T = 100.000$

* $1 ≤ T ≤ 1.000$

* $1 ≤ N ≤ 10^18^$
* $1 ≤ K ≤ 1.000.000$

* $Se garantează că toţi piticii încap în cabană.$

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

| 2
3 2
5 2
| 4
8

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

|
h3. Explicaţie

Pentru primul test, sunt $3$ pitici şi $2$ camere. Cele patru posibilităţi sunt:
1. Camera $1$ este ocupată de piticii $1$ şi $3$, iar camera $2$ de piticul $2$.
2. Camera $1$ este ocupata de piticul $1$, iar camera $2$ de piticii $2$ şi $3$.
3. Camera $1$ este ocupata de piticul $2$ şi $3$, iar camera $2$ de piticul $1$.
4. Camera $1$ este ocupata de piticul $2$, iar camera $2$ de piticii $1$ şi $3$.

...

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

9412