#include<cstdio>
#define je 1000000007
long long fact[1000001];
long long gop(long long x,long long y){
x%=je;y%=je;
x*=y;x%=je;
return x;
}
long long hap(long long x,long long y){
x%=je;y%=je;
x+=y;x%=je;
return x;
}
long long div(long long x,long long y){
x%=je;y%=je;
int left=je-2;
long long gopp=y,ret=1;
while(left){
if(left&1){
ret=gop(ret,gopp);
}
gopp=gop(gopp,gopp);
left >>= 1;
}
ret=gop(ret,x);
return ret;
}
long long nCr(int n,int k){
return div(div(fact[n],fact[k]),fact[n-k]);
}
int main(){
int n,k;
long long now=1,r,c,ans=0;
scanf("%d %d",&n,&k);
fact[0]=1;
for(int i=1;i<=n;i++){
fact[i]=gop(fact[i-1],i);
}
for(int i=0;i<=n;i++){
if(i>=n-i) ans=hap(ans,gop(now,nCr(i,n-i)));
now=gop(now,k);
}
printf("%lld",ans);
}
