题目链接：http://codeforces.com/contest/622/problem/F
题目大意：

#include<bits/stdc++.h>

#define LL long long
using namespace std;
const int mod = 1e9+7;

#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
const int D=1e6+10;
LL a[D],f[D],g[D],p[D],p1[D],p2[D],b[D],h[D][2],C[D];
LL powmod(LL a,LL b){LL res=1;a%=mod;assert(b>=0);for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
//..........................
//已知f(0),f(1)..f(d) 求 f(n)
LL calcn(int d,LL *a,LL n) { // a[0].. a[d] a[n]
    if (n<=d) return a[n];
    p1[0]=p2[0]=1;
    rep(i,0,d+1) {
        LL t=(n-i+mod)%mod;
        p1[i+1]=p1[i]*t%mod;
    }
    rep(i,0,d+1) {
        LL t=(n-d+i+mod)%mod;
        p2[i+1]=p2[i]*t%mod;
    }
    LL ans=0;
    rep(i,0,d+1) {
        LL t=g[i]*g[d-i]%mod*p1[i]%mod*p2[d-i]%mod*a[i]%mod;
        if ((d-i)&1) ans=(ans-t+mod)%mod;
        else ans=(ans+t)%mod;
    }
    return ans;
}
// 初始化，初始化的时候记得将D的值
void init(int M) {
    f[0]=f[1]=g[0]=g[1]=1;
    rep(i,2,M+5) f[i]=f[i-1]*i%mod;
    g[M+4]=powmod(f[M+4],mod-2);
    per(i,1,M+4) g[i]=g[i+1]*(i+1)%mod;
}
//已知 f(0),f(1)...f(m),求 \sum_{i=0 }^{n} f[i]
LL polysum(LL m,LL *a,LL n) { // a[0].. a[m]

    for(int i=0;i<=m;i++) b[i]=a[i];
    b[m+1]=calcn(m,b,m+1);
    rep(i,1,m+2) b[i]=(b[i-1]+b[i])%mod;
    return calcn(m+1,b,n);// m次多项式的和是m+1 次多项式
}

LL qpolysum(LL R,LL n,LL *a,LL m) {
// a[0].. a[m] \sum_{i=0}^{n-1} a[i]*R^i
    if (R==1) return polysum(n,a,m);
    a[m+1]=calcn(m,a,m+1);
    LL r=powmod(R,mod-2),p3=0,p4=0,c,ans;
    h[0][0]=0;h[0][1]=1;
    rep(i,1,m+2) {
        h[i][0]=(h[i-1][0]+a[i-1])*r%mod;
        h[i][1]=h[i-1][1]*r%mod;
    }
    rep(i,0,m+2) {
        LL t=g[i]*g[m+1-i]%mod;
        if (i&1) p3=((p3-h[i][0]*t)%mod+mod)%mod,p4=((p4-h[i][1]*t)%mod+mod)%mod;
        else p3=(p3+h[i][0]*t)%mod,p4=(p4+h[i][1]*t)%mod;
    }
    c=powmod(p4,mod-2)*(mod-p3)%mod;
    rep(i,0,m+2) h[i][0]=(h[i][0]+h[i][1]*c)%mod;
    rep(i,0,m+2) C[i]=h[i][0];
    ans=(calcn(m,C,n)*powmod(R,n)-c)%mod;
    if (ans<0) ans+=mod;
    return ans;
}
// polysum::init();

LL b1[100];
int main(){

    LL n, k;
    scanf("%lld%lld", &n, &k);
    if(k == 0){
        printf("%lld",n);
        return 0;
    }
    init(k+100);
    b1[0]=0;
    for(int i=1; i<=k+1; i++){
        b1[i]=powmod(i, k);
    }
    LL ans=polysum(k,b1,n);
    cout<<ans<<endl;

    return 0;

}