快速幂

/* 核心思想：分治
a^b = a*a*...*a  //b个a相乘 
	= (a*a)*(a*a)*...*(a*a)*(a*a)  //b为偶数，即 b%2==0  b/2个(a*a)相乘 
	= [(a*a)*(a*a)]*...[(a*a)*(a*a)]  //逐级合并 a   b/2/2个[(a*a)*(a*a)]相乘
	【或= (a*a)*(a*a)*...*a  //b为奇数，即 b%2==1  (b/2)的整数部分个(a*a)相乘
		= [(a*a)*(a*a)]*...[(a*a)*(a*a)]*a  //逐级合并 a  】

eg. b=2, p=5, k=3
b^p = 2^5  //b = 2
	= 2*2*2*2*2  //p(=5)%2==1，a = a*b = 1*2 = 2，p/2 = 5/2 = 2
	= (2*2)*(2*2)*2  //b = b*b = 2*2 = 4
	= 4*4*2  //p(=2)%2==0，a = 2，p/2 = 2/2 = 1
	= (4*4)*2  //b = b*b = 4*4 = 16
	= 16*2  //p(=1)%2==1，a = a*b = 2*16 = 32，p/2 = 1/2 = 0 【循环结束】 
	= 32
*/

#include<cstdio>
using namespace std;

int main(){
    long long a=1, b, p, k;
    scanf("%lld%lld%lld", &b, &p, &k);
     
    /* 补充一个定理：a*b%p = (a%p)*(b%p)%p
    由此定理，为了防止 long long 溢出，每一次 *b 后可以执行 %k 操作 
	*/ 
    while(p){
    	if(p%2) a = a*b%k; 
        b = b*b%k; 
        p /= 2;
    }
    
    printf("%lld\n", a%k);

    return 0;
}