Mr. Meseeks has just turned evil and is on his way to destroy the universe. To stop him Rick and Morty need to buy some time and keep him busy. So, Morty gives Mr. Meseeks a set A with n elements and tells him to make k non-empty sets B1, B2, ... Bk - 1, Bk such that Bk ⊆ Bk - 1⊆ Bk - 2 ⊆...B1⊆ A.
Rick wonders in how many ways Mr. Meseeks can make the sets. Now, Given n and k, your task is to help Rick determine that.
Input
Input starts with an integer T, denoting the number of test cases. Each of the next T lines contain two integers n and k as stated in description.
Constraints
1 <= T <= 100000
1 <= n <= 2000000000
1 <= k <= 2000000000
Output
For each case, you have to print the number of ways Mr. Meseeks can make the sets modulo 1000000007.
Sample
| Input | Output |
|---|---|
2 3 1 2 3 | 7 7 |
Explanation of Case 2.
Let A = {a, b}
Then the possible ways are -
{a} ⊆ {a} ⊆ {a} ⊆ {a, b}
{a} ⊆ {a} ⊆ {a, b} ⊆ {a, b}
{a} ⊆ {a, b} ⊆ {a, b} ⊆ {a, b}
{b} ⊆ {b} ⊆ {b} ⊆ {a, b}
{b} ⊆ {b} ⊆ {a, b} ⊆ {a, b}
{b} ⊆ {a, b} ⊆ {a, b} ⊆ {a, b}
{a, b} ⊆ {a, b} ⊆ {a, b} ⊆ {a,b}
