Pablo has N safe houses. Each safe house is located in a different city & these cities are numbered from 1 to N. Each city is connected to every other city & any city can be reached from every other city in a single day.

Safe house located in city 1 is Pablo's favorite due to it's maximum security, so, initially Pablo will be at this safe house. Agent Murphy of DEA wants to catch Pablo & Pablo somehow gets the information that Agent Murphy knows that he is in Safe House of city 1.



So, Pablo decided to move to other safe houses & he will change his safe house every day for the next K days. But he is not sure in which order he should move to different safe houses. So, your task is to help Pablo by determining the number of ways in which he can end up at safe house of city 1 by changing safe house every day for the next K days.

INPUT :

• First line contains an integer T denoting the number of test case(s).
• Next T lines consists of two space separated integers representing N & K respectively.

OUTPUT :

• For each test case print answer modulo 1000000007 (10^9 + 7) in a separate line.

CONSTRAINTS

• 1 ≤ T ≤ 10⁵
• 1 ≤ N ≤ 10⁹
• 1 ≤ K ≤ 10¹⁸