题解
总共情况有$M^N$种
不会越狱的情况有$M\times (M-1)^{N-1}$种。
前者减去后者即为答案。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
using namespace std;
typedef long long ll;
ll n,m,P=100003;
ll qpow(ll a,ll b){
ll res=1;
while(b){
if(b&1)res=(res*a)%P;
a=(a*a)%P,b>>=1;
}
return res;
}
void init(){
scanf("%lld%lld",&m,&n);
m%=P;
}
void solve(){
ll ans=qpow(m,n),ans2=qpow(m-1,n-1);
ans2=(ans2*m)%P;
ans=(ans+P-ans2)%P;
printf("%lld\n",ans);
}
int main(){
init();
solve();
return 0;
}