D. Darts
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

TFG loves to play BloonsTD6 while he's not solving problems in CodeForces. Unfortunately, he is tired of mindlessly popping balloons. He wants to know the exact number of darts required to win the great balloons war challenge. He already knows that for each round he plays, there are $$$n$$$ hordes of balloons. In the first horde, there is one balloon; in the second horde, there are two balloons; and so on until the $$$n$$$th horde, where there are $$$n$$$ balloons. To defeat a horde with $$$i$$$ balloons, TFG has to shoot $$$i^k$$$ darts, where $$$k$$$ is the balloons' power level.

TFG quickly realized that doing all the math would be too boring for him. Luckily, his friend Lucas figured out that by knowing the number of darts needed to win a balloon battle with power level $$$k$$$, you can calculate the number of darts needed for power level $$$k+1$$$ using the formula:

$$$$$$S_k = \frac{1}{k+1} \left( (1+n)^{k+1} - n - 1 - \sum_{i=1}^{k-1} \binom{k+1}{i} S_i \right)$$$$$$

Unfortunately, Lucas is too busy training for the next ICPC stage to calculate the actual number for TFG, so he has asked for your help.

Please help TFG figure out how many darts he needs to end the war.

Since the answer can be large, print it modulo $$$10^9 + 7$$$.

Input

Each test consists of multiple test cases. The first line contains a single integer $$$t (1 \le t \le 100)$$$ — the number of test cases. The description of the test cases follows.

The only line of each test case contains two integers $$$n (1 \le n \le 10^9)$$$ — the number of hordes in the battle and $$$k (1 \le k \le 10^3)$$$ — the balloons power level.

Output

For each test case, output a single line with the integer $$$S_k$$$ modulo $$$10^9 + 7$$$, the number of darts required to win the level.

Examples
Input
1
10 1
Output
55
Input
5
10 2
10 3
100 2
8 3
5 5
Output
385
3025
338350
1296
4425