Solve the programming task below in a Python markdown code block.
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$