#include <stdio.h>
#include <iostream>
using namespace std;
int modexp(int x, int y, int N)
{
if (y == 0) return 1;
int z = modexp(x, y / 2, N);
if (y % 2 == 0)
return (z*z) % N;
else
return (x*z*z) % N;
}
int main()
{
int x, y, N;
cout << "x= "; cin >> x;
cout << "y= "; cin >> y;
cout << "N= "; cin >> N;
cout << modexp(x, y, N);
cin.get(); cin.get();
return 0;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxpb3N0cmVhbT4KCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgppbnQgbW9kZXhwKGludCB4LCBpbnQgeSwgaW50IE4pCnsKICBpZiAoeSA9PSAwKSByZXR1cm4gMTsKICBpbnQgeiA9IG1vZGV4cCh4LCB5IC8gMiwgTik7CiAgaWYgKHkgJSAyID09IDApCiAgICByZXR1cm4gKHoqeikgJSBOOwogIGVsc2UKICAgIHJldHVybiAoeCp6KnopICUgTjsKfQppbnQgbWFpbigpCnsKICBpbnQgeCwgeSwgTjsKICBjb3V0IDw8ICJ4PSAiOyBjaW4gPj4geDsKICBjb3V0IDw8ICJ5PSAiOyBjaW4gPj4geTsKICBjb3V0IDw8ICJOPSAiOyBjaW4gPj4gTjsKICBjb3V0IDw8IG1vZGV4cCh4LCB5LCBOKTsKICBjaW4uZ2V0KCk7IGNpbi5nZXQoKTsKICByZXR1cm4gMDsKfQ==