3621 - 越狱

2 3

6

Solution C++

#include<iostream>
#include<cstdio>
using namespace std;
long long f(long long m,long long n)
{
	if(n==0)
	    return 1;
	long long t=f(m,n/2)%100003;
	if(n%2==0)
	    return (t*t)%100003;
	else
	    return (t*t*m)%100003;
}
int main()
{
    //freopen("prison.in","r",stdin);
	//freopen("prison.ans","w",stdout);
	long long m,n;
	cin>>m>>n;
	m%=100003;
	cout<<(f(m,n)-f(m-1,n-1)*m%100003+100003)%100003;
	return 0;
}