越狱（信息学奥赛一本通 1618）

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const long long M=100003;
 4 long long m,n;//这道题基本上都是用long long类型，不然会像我一样被卡5个点死活过不去ε(┬┬﹏┬┬)3
 5 long long read()
 6 {
 7     long long x=0,f=1;
 8     char ch=getchar();
 9     while(ch<‘0‘||ch>‘9‘)
10     {
11         if(ch==‘-‘) f=-1;
12         ch=getchar();
13     }
14     while(ch>=‘0‘&&ch<=‘9‘)
15     {
16         x=x*10+ch-‘0‘;
17         ch=getchar();
18     }
19     return x*f;
20 }
21 void write(int x)
22 {
23     if(x<0)
24     {
25         putchar(‘-‘);
26         x=-x;
27     }
28     if(x>9) write(x/10);
29     putchar(x%10+‘0‘);
30 }
31 
32 long long ff(long long x,long long y)
33 {
34     long long ans=1;
35     while(y)
36     {
37         if(y&1)ans=ans*x%M;
38         x=x*x%M;
39         y>>=1;
40     }
41     return ans;
42 }
43 int main()
44 {
45     m=read();n=read();
46     if(n<2)return 0*puts("0");
47     printf("%lld\n",((ff(m,n)-m*ff(m-1,n-1)%M)%M+M)%M);
48     return 0;
49 }