Anmol and Biswa have got a water gun with colored pellets to hit Anurag as they have too much free time this semester. The pellets can be of K different colors. They have infinite pellets for each color. The water gun has only two slots for pellets, both of which get fired simultaneously(i.e., the order of pellets in the refill does not matter). So they'll have to refill it a number of times. On each refill, they must choose two pellets, which must be of different colors. They aren't worried about that though, as both of them have whole of their afternoon free now.
Now, they decided to refill the gun N times, and want each refill be such that any pair of refill of pellets out of those N has atleast one color in common between them. They now start wondering how many such ordered sets of refills exist.
Mathematically, the refills, $R_{i}$ are such that, $R_{1},R_{2},...,R_{N}, |R_{i}| = 2, R_i \subseteq$ {$1,2,...K$} and $R_{i} \bigcap R_{j} \not= \Phi$ for any distinct $i,j \in$ [$1,2,..N$] .

Note: Print the number of such ordered sets of refills modulo 1000000007.

Input

• The first line contains a single integer T, denoting the number of test cases.
• Next T lines contain two space separated integers K and N denoting the number of colors for the pellets and number of refills respectively.

• For each test case, you need to output a single integer in a new line.

• 1 ≤ T ≤ 1000
• 1 ≤ N ≤ 5000
• 1 ≤ K ≤ 5000