#include<bits/stdc++.h>

#define reg register int

#define il inline

#define numb (ch^'0')

using namespace std;

typedef long long ll;

il void rd(int &x){

    char ch;x=;bool fl=false;

    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);

    for(x=numb;isdigit(ch=getchar());x=x*+numb);

    (fl==true)&&(x=-x);

}

namespace Miracle{

const int N=;

const int mod=1e9+;

ll C[N][N];

int n,m;

ll f[N];

ll qm(ll x,ll y){

    ll ret=;

    while(y){

        if(y&) ret=ret*x%mod;

        x=x*x%mod;

        y>>=;

    }

    return ret;

}

int main(){

    rd(n);rd(m);

    if(m==){

        ll ans=((ll)n*(n+))%mod*qm(,mod-)%mod;

        printf("%lld",ans);

        return ;

    }

    C[][]=;

    for(reg i=;i<=m;++i){

        C[i][]=;

        for(reg j=;j<=m;++j){

            C[i][j]=(C[i-][j]+C[i-][j-])%mod;

        }

    }

    f[]=m*(qm(m,n)-+mod)%mod*qm(m-,mod-)%mod;

    for(reg i=;i<=m;++i){

        for(reg j=;j<=i-;++j){

            if((i-j)&){

                f[i]=(f[i]-C[i][j]*f[j]%mod+mod)%mod;

            }else{

                f[i]=(f[i]+C[i][j]*f[j]%mod)%mod;

            }

        }

        f[i]=(f[i]+qm(n,i)*qm(m,n+)%mod)%mod;

        f[i]=(f[i]*qm(m-,mod-))%mod;

    }

    printf("%lld",f[m]);

    return ;

}

}

signed main(){

    Miracle::main();

    return ;

}

/*

   Author: *Miracle*

   Date: 2018/12/29 16:48:22

*/