快速幂
大水题= =
正着找越狱情况不好找，那就反过来找不越狱的情况呗……
总方案是$m^n$种，不越狱的有$m*(m-1)^{n-1}$种= =
负数搞搞就好了……
莫名奇妙地T了好几发……
/**************************************************************
Problem: 1008
User: Tunix
Language: C++
Result: Accepted
Time:0 ms
Memory:804 kb
****************************************************************/ //BZOJ 1008
#include<cstdio>
typedef long long LL;
const int P=;
LL Pow(LL a,LL b,LL P){
LL r=;
for(;b;b>>=,a=a*a%P) if (b&) r=r*a%P;
return r;
}
int main(){
LL n,m;
scanf("%lld%lld",&m,&n);
LL ans=Pow(m,n,P)-Pow(m-,n-,P)*m%P;
if (ans<) ans+=P;
printf("%lld\n",ans);
return ;
}