整体类似快速幂，在第63个点wa了 https://codeforces.com/gym/104619/problem/E

#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
ull a,b,m;
map<ull,ull>mp;
ull gsc(ull a,ull b)
{
	ull res=0;
	for(;b;b>>=1,a=(a+a)%m)
		if(b&1)res=(res+a)%m;
	return res;
}
unsigned long long f(unsigned long long x){
	if(x==1) return a%m;
	if(mp[x])return mp[x];
	ull tmp=f(x/2)%m;
	if(x%2==0) return mp[x]=(gsc(tmp,tmp)-2%m+m)%m;
	else return mp[x]=(gsc(tmp,f(x/2+1))-a%m+m)%m;
}
int main(){
	
	cin>>a>>b>>m;
	if(b==0)cout<<2;
	else cout<<f(b)<<endl;
	return 0;
} 
/*
18446744073709551615 18446744073709551615 18446744073709551615
1000000000000000000 1000000000000000000 1000000000000000000
*/