#include <iostream>
#include <fstream>
using namespace std;
long rep_sq(int b, int p)
{
if(p==1) return b;
if(p%2==0)
return rep_sq(b*b, p/2);
else
return b * rep_sq(b*b, (p-1)/2);
}
long int big_mod(int b, int p, int m)
{
if(b==0) return 0;
if(p==1) return b%m;
if(p%2 == 0)
return big_mod(b, p/2, m)%m * big_mod(b, p/2, m)%m;
else
return (b%m) * big_mod((b%m)*(b%m), (p-1)/2, m)%m;
}
int main()
{
int b, p, m;
while( cin >> b )
{
cin >> p;
cin >> m;
cout << big_mod(b, p, m) << endl;
}
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8ZnN0cmVhbT4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmxvbmcgcmVwX3NxKGludCBiLCBpbnQgcCkKewogICAgICAgIGlmKHA9PTEpIHJldHVybiBiOwogICAgICAgIGlmKHAlMj09MCkKICAgICAgICAgICAgICAgIHJldHVybiByZXBfc3EoYipiLCBwLzIpOwogICAgICAgIGVsc2UKICAgICAgICAgICAgICAgIHJldHVybiBiICogcmVwX3NxKGIqYiwgKHAtMSkvMik7Cn0KCmxvbmcgaW50IGJpZ19tb2QoaW50IGIsIGludCBwLCBpbnQgbSkKewogICAgICAgIGlmKGI9PTApIHJldHVybiAwOwogICAgICAgIGlmKHA9PTEpIHJldHVybiBiJW07CiAgICAgICAgaWYocCUyID09IDApCiAgICAgICAgICAgICAgICByZXR1cm4gYmlnX21vZChiLCBwLzIsIG0pJW0gKiBiaWdfbW9kKGIsIHAvMiwgbSklbTsKICAgICAgICBlbHNlCiAgICAgICAgICAgICAgICByZXR1cm4gKGIlbSkgKiBiaWdfbW9kKChiJW0pKihiJW0pLCAocC0xKS8yLCBtKSVtOwoKfQoKaW50IG1haW4oKQp7CiAgICAgICAKICAgICAgICBpbnQgYiwgcCwgbTsKICAgICAgICB3aGlsZSggY2luID4+IGIgKQogICAgICAgIHsKICAgICAgICAgICAgICAgIGNpbiA+PiBwOwogICAgICAgICAgICAgICAgY2luID4+IG07CgogICAgICAgICAgICAgICAgY291dCA8PCBiaWdfbW9kKGIsIHAsIG0pIDw8IGVuZGw7CiAgICAgICAgfQoKICAgICAgICByZXR1cm4gMDsKfQo=
MwoxODEzMgoxNwoKMTcKMTc2NQozCgoyMzc0ODU5CjMwMjkzODIKMzYxMjMKCjMKMTUKNAoKMAoyMTQ3NDgzNjQ3CjEwCgoyMTQ3NDgzNjQ3CjIxNDc0ODM2NDcKMTAKCjIxNDc0ODM2NDcKMjE0NzQ4MzY0Nwo0NjM0MAoKMAowCjEK
3
18132
17
17
1765
3
2374859
3029382
36123
3
15
4
0
2147483647
10
2147483647
2147483647
10
2147483647
2147483647
46340
0
0
1