算法很容易想到，但是就是范围太搞人了。本人技术欠佳，想不到更优秀的算法了。只有拿更大的数据类型来存，避免了这个问题。（仅限本题目的情况，刚好卡在这个测试数据范围，其它超出数据范围的一概不知）

#include <bits/stdc++.h>

long long func(__int128 q, __int128 n, __int128 mod)
{
	__int128 ans = 1,a = q % mod;
	while(n)
	{
		if(n & 1)
		{
			ans = ans * a % mod;
		}
		a = a * a % mod;
		n >>= 1;
	}
	return ans;
}

int main()
{
	long long a, b, c;
	while(~scanf("%lld %lld %lld", &a, &b, &c))
	{
		printf("%lld\n",func(a,b,c));
	}
}