aaaaaaaaaaaa

#include <iostream>
using namespace std;
typedef long long ll;

ll fast_pow(ll a, ll b, ll p) {
if (b == 0) return 1 % p; // 边界：a^0 = 1，记得对 p 取模
ll half = fast_pow(a, b / 2, p); // 递归求 a^(b/2)
half = half * half % p; // 平方取模
if (b % 2 == 1) // b 为奇数，再乘一个 a
half = half * a % p;
return half;
}

int main() {
ll a, b, p;
cin >> a >> b >> p;
cout << a << "^" << b << " mod " << p << "=" << fast_pow(a, b, p) << endl;
return 0;
}