#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;
ifstream f("lgput.in");
ofstream g("lgput.out");
int n,p;
long long PutereLogaritmic(long long x, int n)
{
	long long p = 1 ;
	while (n > 0)
	{
		if (n & 1) // n este impar
		{
			p *= x;
			p=p%100003;
			n-- ;
		}
		x = x * x  ;
		x=x%100003;
		n >>= 1 ; // sau n = n / 2
	}
	return p;
}
int main()
{
    f>>n>>p;
    g<<PutereLogaritmic(n,p);
    return 0;
}