There are N Hostels in IIT Roorkee. As Cognizance is coming administration wants to color all the hostels.
Hostels are numbered from 1 to n from left to right. Pendu has been assigned to this job. He has m color boxes(numbered from 1 to m) each containing different colors.
Each hostel can be colored only once. He will use every color to color at least one hostel. Hostels have to be colored in increasing order of their hostel numbers (leftmost to rightmost).
Pendu uses following way to color the hostels. 
He opens the color box#1 and starts coloring the hostels from hostel number 1. He can color as many hostels he wants from this color and after finished coloring from this color, he closes the box. The catch is that once the box closed, he can't reopen it. He has to open next box (if he has) i.e box#2 and start coloring the house next to the house he has just colored and the same goes on.
Now Pendu is very lazy, instead of coloring, he starts wondering in how many different ways he can color hostels.
Two ways are different if there is hostel which is colored in different colors in both ways.
Let f(n,m) be number of ways to color n hostels with m colors using this way . Pendu wants to know the value of
f(n,m)+f(n-1,m-1)+f(n-2,m-2).......+f(n-m+1,1).Output it modulo 10^9+7.

Input Format
First line contains an integer T denoting the number of test cases.
Each test case contains an integer n and m.
Output Format
For each test case output exactly one number.
Input Constraints
1<=T<=100000
1<=n<=100000
1<=m<=n