Easy Summation
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)Total Submission(s): 801 Accepted Submission(s): 294
Problem Description
You are encountered with a traditional problem concerning the sums of powers.
Given two integers $n$ and $k$. Let $f(i)=i^k$, please evaluate the sum $f(1)+f(2)+...+f(n)$. The problem is simple as it looks, apart from the value of $n$ in this question is quite large.
Can you figure the answer out? Since the answer may be too large, please output the answer modulo $10^9+7$.
Given two integers $n$ and $k$. Let $f(i)=i^k$, please evaluate the sum $f(1)+f(2)+...+f(n)$. The problem is simple as it looks, apart from the value of $n$ in this question is quite large.
Can you figure the answer out? Since the answer may be too large, please output the answer modulo $10^9+7$.
Input
The first line of the input contains an integer $T(1\leq T\leq20)$, denoting the number of test cases.
Each of the following $T$ lines contains two integers $n(1\leq n\leq 10000)$ and $k(0\leq k\leq 5)$.
Each of the following $T$ lines contains two integers $n(1\leq n\leq 10000)$ and $k(0\leq k\leq 5)$.
Output
For each test case, print a single line containing an integer modulo $10^9+7$.
Sample Input
3 2 5 4 2 4 1
Sample Output
33 30 10