"""练习 13：用倍增法计算 a 的 n 次幂对 m 取模。
输入一行三个整数 a、n、m，其中 n >= 0、m > 0。

学习说明：
- 普通逐次乘法需要做约 n 次；倍增法每次把指数除以 2，步骤约为 log2(n)。
- result 累积答案，base 是当前底数的幂，exponent 是还没有处理的指数。
- 指数为奇数时，先把当前 base 乘进 result；随后 base 平方，指数整除 2。
- 每次乘法后都取模，避免计算巨大的完整 a 的 n 次幂。
"""
a, n, m = map(int, input().split())
if n < 0 or m <= 0:
    raise ValueError("要求 n >= 0 且 m > 0")

result = 1 % m
base = a % m
exponent = n
# 指数每轮至少减半，最终会变成 0，循环因而结束。
while exponent > 0:
    if exponent % 2 == 1:
        result = result * base % m
    base = base * base % m
    exponent //= 2

print(result)