Christmas is still months away but phoebe is over enthusiastic for it. She plans to buy N ornaments(balls), each of different colors and make K christmas trees from it. As she gets confused with the designs, she wants to know all possible number of arrangements of those ornaments to form exactly K trees. Each tree has to pivoted so the root of the pivot effects the arrangement of the tree. Also since the number of possible arrangements can be very large output modulo 1000000007.
Input
First line will contain a single integer T denoting number of test cases.
Next T lines will contain two integers N and K denoting number of ornaments and number of trees respectively.
Output
For each test case print number of possible arrangements.
Input Constraints
1 <= T <= 106
1<= K < N <= 106
