#include <bits/stdc++.h>

using namespace std;

const int mo=1e9+;

#define IL inline

#define ll long long

#define rint register int

#define rep(i,h,t) for (rint i=h;i<=t;i++)

#define dep(i,t,h) for (rint i=t;i>=h;i--)

const int N=2e6;

ll f[N],jc[N];

ll fst(ll x,ll y)

{

  if (y==) return();

  if (y==) return(x);

  ll kk=fst(x,y/);

  kk=(kk*kk)%mo;

  if (y%) kk=(kk*x)%mo;

  return kk;

}

int main()

{

  freopen("1.in","r",stdin);

  freopen("1.out","w",stdout);

  ios::sync_with_stdio(false);

  ll n,k;

  cin>>n>>k;

  rep(i,,k+)

    f[i]=(f[i-]+fst(i*1ll,k))%mo;

  if (n<=k+)

  {

    cout<<f[n]<<endl;

    return ;

  }

  jc[]=;

  rep(i,,k+) jc[i]=(jc[i-]*i)%mo;

  ll now=,ans=;

  rep(i,,k+) now=(now*(n-i))%mo;

  rep(i,,k+)

  {

    ll inv1=fst(n-i,mo-);

    ll inv2=fst((jc[i-]*jc[k+-i])%mo,mo-)%mo;

    ll sign=(k+-i)%?-:;

    ans=(ans+sign*inv1*inv2%mo*f[i]%mo*now%mo)%mo;

  }

  cout<<(ans+mo)%mo;

  return ;

}