Contest1242/G.cpp

#include<bits/stdc++.h>
using namespace std;
const int M=1000;
int f(int a,int b) {
	a%=M;
	if(a==1||b==0)
		return 1;
	if(b%2==0) {
		return f(a*a%M,b/2);
	} else {
		return (a*f(a*a%M,b/2))%M;
	}

}
int main() {
	int a,b;
	while(cin>>a>>b) {
		cout<<setw(3)<<setfill('0')<<f(a,b)<<endl;
	}
	return 0;
}