#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10,INF = 0x3f3f3f3f;;
typedef pair<int, int> PII;

int n,m,n2;      // 点的数量
int st[N];     // 存储每个点的最短距离是否已确定
long long qpow(long long a,ll k,int p)
{
	ll res=1;
	while(k)
	{
		if(k&1)
		{
			res=(ll)res*a%p;
		}
		k>>=1;
		a=(ll)a*a%p;
	}
	return res?res:p;
}
int main()
{
//	ios::sync_with_stdio(false);
//    cin.tie(0);
//    cout.tie(0);
    long long a=0,k=0;
    int p=0;
	while(cin>>a>>k>>p)
	{
		
		ll res=qpow(a,k,p-1);
        cout<<res<<endl;
	}
    
	return 0;	
}

分析题意：已知N，求N'

N = a0 + a1*k + a2*k^2 +...

N' = a0 + a1 + a2+ ...

两式相减能够得到N-N'被k-1整除。
所以N' = N%(k-1)，转化为快速幂问题，此外，N' = k-1这种情况会在N%(k-1)中算为0，所以加一个条件判断