Cabana

cabana

== 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:
 
* 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?
 
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$*.

Poveste şi cerinţă...

h2. Date de intrare

Fişierul de intrare $cabana.in$ conţine pe prima linie un număr natural $T$, reprezentând numărul de teste. Pe urmatoarele $T$ linii, se vor găsi două numere $N$ şi $K$, având semnificaţia din enunţ.

Fişierul de intrare $cabana.in$ ...

h2. Date de ieşire

În fişierul de ieşire $cabana.out$ se vor găsi $T$ linii, pe fiecare linie $i$ găsindu-se răspunsul la întrebarea $i$.

În fişierul de ieşire $cabana.out$ ...

h2. Restricţii

* $T = 100.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