You are given a sequence whose $n^{\text{th}}$ term is

$T_{n}=n^{K}$
You have to evaluate the series
$S_n=T_1+T_2+T_3+\cdots+T_n$
Find $S_n\:\text{mod}\:(10^9+7)$.

Input Format

The first line of input contains $\mathbf{T}$, the number of test cases.

Each test case consists of one line containing two space-separated integers $n$ and $\mbox{K}$.

Output Format

For each test case, print the required answer in a line.

Constraints

$1\leq T\leq10$

$0\leq K\leq10^3$

$1\leq n\leq10^{16}$

Sample Input

3
5 3
4 2
4 1

Sample Output

225
30
10

Explanation

Case 1: We have $225=1^3+2^3+3^3+4^3+5^3$

Case 2: We have $30=1^2+2^2+3^2+4^2$

Case 3: We have $10=1^1+2^1+3^1+4^1$

见题面

见题面