可以分治，将 $a^n$ 变成 $a^{frac{n}{2}}\times a^{frac{n}{2}}$，但如果此时 $n$ 是奇数，则多乘一个 $a$。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a,b,p=1e9+7;
ll qpow(ll a,ll b,ll p){
	ll res=1,tmp=a;
	while(b){
		if(b&1)res=(res%p*tmp%p)%p;
		tmp=(tmp*tmp)%p;
		b>>=1;
	}
	return res;
}
int main(){
	cin>>a>>b>>p;
	cout<<qpow(a,b,p)<<endl;
	return 0;
}