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ă cel puţin o cameră conţine alţi pitici.

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

9412