You are encountered with a traditional problem concerning the sums of powers.
Given two integers
n
n and
k
k. Let
f(i)=ik
f(i)=ik, please evaluate the sum
f(1)+f(2)+...+f(n)
f(1)+f(2)+...+f(n). The problem is simple as it looks, apart from the value of
n
nin this question is quite large.
Can you figure the answer out? Since the answer may be too large, please output the answer modulo
109+7
109+7.
Input
The first line of the input contains an integer
T(1≤T≤20)
T(1≤T≤20), denoting the number of test cases.
Each of the following
T
T lines contains two integers
n(1≤n≤10000)
n(1≤n≤10000) and
k(0≤k≤5)
k(0≤k≤5).
Output
For each test case, print a single line containing an integer modulo
109+7
109+7.
Sample Input
3
2 5
4 2
4 1
Sample Output
33
30
10
这个题的数据量是很大的，因此每求一次a^b,都要进行取模，所以我们把pow()函数在这儿重新写 一次，同时，最后的输出结果也要取模。
#include <iostream>
#include<cstdio>
#include<cmath>
using namespace std;
const int N=
1000000000+
7;
long long pow1(int a,int b)
{
long long p=
1;
for(
int i=
1;i<=b;i++)
{
p*=a;
p%=N;
}
return p;
}
int main()
{
int T;
scanf(
"%d",&T);
while(T--)
{
long long a,b,sum=
0;
scanf(
"%lld%lld",&a,&b);
for(
int i=
1;i<=a;i++)
sum+=pow1(i,b);
printf(
"%lld\n",sum%N);
}
return 0;
}
