#include<bits/stdc++.h>
#define ll long long
using namespace std;

ll b,p,k;

ll pow(ll b,ll p)
{
	if(p==0) return 1;
	if(p==1) return b;
	int a=pow(b,p/2)%k;
	if(p%2==1) return (a*a*b)%k;
	return (a*a)%k;
}

int main()
{
	cin>>b>>p>>k;
	cout<<b<<"^"<<p<<" "<<"mod"<<" "<<k<<"="<<pow(b,p)%k;
	return 0;
}

最后一个数据是这样的

2 1000000000 1000000007

正确输出是

2^1000000000 mod 1000000007=140625001

代码输出了

2^1000000000 mod 1000000007=0

代码比较丑，见谅（）