#include<bits/stdc++.h>

using namespace std;

const int N = 1e6+;

const int mod = 1e9+;

int n,k,p[],inv[],sum[],Ans;

inline int pw(int x,int tot){

    int res=;

    while(tot){

      if(tot&)res=1ll*res*x%mod;

      x=1ll*x*x%mod;

      tot>>=;

    }

    return res;

}

int main(){

    int i,j,t=;

    scanf("%d%d",&n,&k);

    p[]=;

    for(i=;i<=N;i++)p[i]=1ll*p[i-]*i%mod;

    inv[N]=pw(p[N],mod-);

    for(i=N-;i>=;i--)inv[i]=1ll*inv[i+]*(i+)%mod;

    for(i=;i<=k+;i++)sum[i]=(sum[i-]+pw(i,k))%mod;

    if(n<=k+){printf("%d\n",sum[n]);return ;}

    for(i=;i<=k+;i++)t=1ll*t*(n-i)%mod;

    for(i=;i<=k+;i++){

      int res=1ll*sum[i]*t%mod*pw(n-i,mod-)%mod*inv[k+-i]%mod*inv[i-]%mod;

      if((k+-i)&)res=mod-res;

      Ans=(Ans+res)%mod;

    }

    printf("%d\n",Ans);

    return ;

}