Problem Statement:
You are given integer n and k. Return the value of the sum 1^k + 2^k + 3^k + ... + n^k modulo 1000000007.

Input:
The first line of input contains a single integer C denoting the number of test cases. Each of the following C lines consist of one test case. Each test case is of the form "n k" where n and k are positive integers.

Input Constraints:
n will be between 1 and 1000000000, both inclusive.
k will be between 1 and 50, both inclusive.

Output:
For each test case, output one line containing the sum 1^k + 2^k + ... + n^k modulo 1000000007.
 
Sample Input:
4
5 1
4 2
13 5
123456789 1

Output for Sample Input
15
30
1002001
383478132