#include<iostream>
using namespace std;

typedef long long LL;

LL qmi(LL a,LL b,LL p)
{
    LL res=0;
    while(b)
    {
        if(b&1)  res=(res+a)%p;
        a=(a<<1)%p;
        b=(b>>1)%p;
    }
    return res%p;
}

int main()
{
    LL a,b,p;
    cin>>a>>b>>p;
    cout<<qmi(a,b,p)<<endl;
    return 0;
}

我们以a*b为例子
任何一个数字都可以写成二进制，比如把b写成2进制 1101
那就是 a*（1*2的0次方+0*2的一次方+1*2的二次方，1*2的三次方）
那就是 a*1*1+a*0*2+a*1*4+a*1*8
也就是 a*1*1+a*2*0+a*4*2+a*8*1
也就是 如果b&1 为1 我们就乘一个base，base的初始值为a，然后每次base*2就好了