#include <fstream>

using namespace std;
ifstream fin ("lgput.in");
ofstream fout ("lgput.out");
long long a,b,ans,pw,i;
int rise(long long a, long long b) {
 if(b == 0) return 1;
 long long x = rise(a, b / 2);
 if(b % 2 == 0) return (x * x) %1000000000 ;
 return (((x * x) % 1000000000) * a) % 1000000000;}
int main()
{fin >> a >> b;


fout<<rise(a,b);
    return 0;
}