#include<stdio.h>
#include<string.h>
//包括了大数加减法
int pow_mod(int x, int y, int z) {
	int ans = 1;
	x = x % z;//z为mod
	while (y > 0) {
		if (y & 1) {//每次将二进制中，是1的位数给取出来
			ans = (ans * x) % z;//
		}
		x = (x * x) % z;//进行下一位
		y = y >> 1;//往右移一位
	}
	return ans;

}
int mod_string(char x[], int z) {
	int result = 0;//返回的结果
	int base = 1;//用于计算每一位，依次乘10

	//从字符串的末尾开始
	int len = strlen(x);//字符串的位数
	for (int i = len - 1; i >= 0; i--) {
		//将每一为，从小到大加入结果，同时进行取余
		result = (result + (x[i] - '0') * base) % z;
		//进行下一位的计算
		//取模的公式都要取模
		base = (base * 10) % z;
	}
	return result;
}
int main() {
	
	char x[105];
	int y, z;
	while (scanf("%s %d %d", &x, &y, &z) != EOF) {
		int x1 = mod_string(x, z);//将一个大数先进行取模
		printf("%d\n", pow_mod(x1, y, z));
	}
	return 0;
}

根据大佬的题解写的