Discription
There are well-known formulas: ,
,
. Also mathematicians found similar formulas for higher degrees.
Find the value of the sum modulo 109 + 7 (so you should find the remainder after dividing the answer by the value 109 + 7).
Input
The only line contains two integers n, k (1 ≤ n ≤ 109, 0 ≤ k ≤ 106).
Output
Print the only integer a — the remainder after dividing the value of the sum by the value 109 + 7.
Example
Input
4 1
Output
10
Input
4 2
Output
30
Input
4 3
Output
100
Input
4 0
Output
4
拉格朗日差值裸题。。。
为什么我以前都用高斯消元做自然幂数和2333333
拉格朗日差值的构造原理和中国剩余定理类似，这里就不在赘述，网上也有很多讲的。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1000010;
const int ha=1000000007;
int jc[maxn+5],TT,l;
int n,k,ans=0,base;
inline int add(int x,int y){
x+=y;
return x>=ha?x-ha:x;
}
inline int ksm(int x,int y){
int an=1;
for(;y;y>>=1,x=x*(ll)x%ha) if(y&1) an=an*(ll)x%ha;
return an;
}
inline void init(){
jc[0]=1;
for(int i=1;i<=maxn;i++) jc[i]=jc[i-1]*(ll)i%ha;
l=k+2,base=1;
}
inline void solve(){
if(n<=l){
for(int i=1;i<=n;i++) ans=add(ans,ksm(i,k));
}
else{
for(int i=1;i<=l;i++) base=base*(ll)(n-i)%ha;
for(int i=1,now;i<=l;i++){
TT=add(TT,ksm(i,k));
now=base*(ll)ksm(n-i,ha-2)%ha*(ll)ksm(jc[i-1],ha-2)%ha*(ll)ksm(jc[l-i],ha-2)%ha;
if((l-i)&1) now=now*(ll)(ha-1)%ha;
ans=add(ans,TT*(ll)now%ha);
}
}
}
int main(){
scanf("%d%d",&n,&k);
init();
solve();
printf("%d
",ans);
return 0;
}