Problem Description

Calculate ∑ni=1im 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

方法：快速冪和大數求和

#include <iostream>using namespace std;
const int d=1000000000+7;
long long poww(long a,long b)
{long long ans=1,base=a;while(b!=0){if(b&1)ans=(ans*base)%d;base=(base*base)%d;b>>=1;}return ans;
}
int main()
{long long n,m;cin>>n>>m;long long sum = 0;for(int i=1;i<=n;i++)sum = (sum+poww(i,m))%d;cout<<sum<<endl;return 0;
}