很少有的思路秒解。题意可以描述成对长度为n的格子有m种染色方案，问存在相邻两个格子同色的方案数，正难则反易，考虑问题的背面任意两个相邻的格子都不同色，第一个格子可以涂任意一种颜色m种可能，剩下的n-1个格子每个不能和前面一个格子相同固有m-1种可能，总的方案数有m^n种，所以答案就是m^n-m（m-1）^n-1 由于答案取模及幂次较高，因此可以考虑小费马定理或快速幂优化
由于数据太2，一开始用 int读成功贡献了3个WA TAT
#include<iostream>
#include<cstdio>
#include <math.h>
using namespace std;
long long ksm(long long k,long long a)
{
if(k==0)return 1;
if(k==1)return a;
if(k % 2 == 0)return ksm(k/2,a)*ksm(k/2,a) % 100003;
else return (ksm(k-1,a)*a) % 100003;
}
int main()
{
long long m=0,n=0,ans;
scanf("%lld%lld",&m,&n);
ans=(ksm(n,m)-(m*ksm(n-1,m-1))% 100003 +100003)%100003;
printf("%lld",ans);
return 0;
}