题目大意：监狱有连续编号为1...N的N个房间，每个房间关押一个犯人，有M种宗教，每个犯人可能信仰其中一种。如果相邻房间的犯人的宗教相同，就可能发生越狱，求有多少种状态可能发生越狱。

好吧这是个数学题。。。

一共有m^n种情况，因为n个人，每个人m种情况，乘法原理，m个n相乘。

不能越狱的有m*(m-1)^(n-1)种情况，因为第一个人随便选，m种；后面的每个人只要不和上一个人一样就行了，还有(n-1)个人，每个人(m-1)种情况。

然后越狱的=总共的-不越狱的

#include<iostream>
#include<cstdio>
using namespace std;
int mod=100003,tot;
long long m,n;
int power(long long a,long long b)
{
	int re=1;
	for(;b;b>>=1,a=a*a%mod)
	  if(b&1)  re=re*a%mod;
	return re;
}
int main()
{
	scanf("%lld%lld",&m,&n);
	tot=(power(m,n)-(m%mod)*power(m-1,n-1)%mod+(m%mod)*mod)%mod;
	printf("%d",tot);
}