其实这道题很简单，连我这么没石粒的都能AC

其实呢，关键就是不要死磕能越狱的可能数 越狱的可能数是什么？ 是总数-不越狱的可能数对吧 那不就简单了嘛？ 直接用m^n算总数(是人都懂) 再用m*(m-1)^(n-1)算出不越狱的可能数(第一个可以选m种宗教，后面的只能选不一样的，才完全不能越狱)不就行了嘛？ 那么算幂的话建议用这个：

unsigned long long qp(unsigned long long x,unsigned long long k)
{
	if(!k) return 1;
	if(k%2) return qp(x,k-1)*x%100003ULL;
	unsigned long long t=qp(x,k/2);
	return t*t%100003ULL;
}

然后直接套公式，取一下模，简简单单~

cout<<(qp(m,n)-m*qp(m-1,n-1)%100003ULL+100003ULL)%100003ULL;

必须在m*(m-1)^(n-1)的时候先取一次模，太大了会WA的 然后就是加上100003再取模，避免负数