山东省第八届 ACM 省赛 sum of power (求和、水)

Problem Description

Calculate $\sum_{i=1}^ni^m~mod~(1000000000+7)$ for given n,m.

 

Input

Input contains two integers n,m(1≤n≤1000,0≤m≤10).

 

Output

Output the answer in a single line.

 

Example Input

10 0

 

Example Output

10

 

思路

绝不应该错的一道题,比赛时第一道敲的题目,居然 1WA 了,原因时题面上写的 mod=100000000+7 ,当时已经写出 1e9+7 ,然后检查的时候发现差点交错,改成 1e8+7 之后就错了。

还好之后这道题重判了,减少了20分钟的罚时。

会不会 100000000+7=1e9+7 呢?

 

AC 代码

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<iostream>
using namespace std;
#include<queue>
#include<map>
#define eps (1e-8)
const int mod = 1e9+7;
typedef long long LL;

LL mult(LL a,LL n)
{
    LL ans=1;
    while(n)
    {
        if(n&1)ans=(ans*a)%mod;
        a=(a*a)%mod;
        n>>=1;
    }
    return ans;
}

int main()
{
    LL n,m;
    while(cin>>n>>m)
    {
        LL ans=0;
        for(LL i=1; i<=n; i++)
            ans=(ans+mult(i,m))%mod;
        cout<<ans<<endl;
    }
    return 0;
}