#include<bits/stdc++.h>
#include<cmath>
#define mem(a,b) memset(a,b,sizeof a);
using namespace std;
typedef long long ll;
/* 快速模幂 - 详解
对于任何一个整数的模幂运算：
a^b%c
对于b可以拆成二进制的形式（b0对应的是b二进制的第一位）：
b=b0+b1*2+b2*2^2+...+bn*2^n
那么我们的a^b运算就可以拆解成：
a^b0 * a^(b1*2^1) *...* a^(bn*2^n)
对于b来说，二进制位不是0就是1，那么对于bx为0的项我们的计算结果是1就不用考虑了，我们真正想要的其实是b的非0二进制位。
那么假设除去了b的0的二进制位之后我们得到的式子是：
a^(bx*2^x) *...* a(bn*2^n)
这里我们再应用我们一开始提到的公式，那么我们的a^b%c运算就可以转化为：
(a^(bx*2^x)%c) *...* (a^(bn*2^n)%c)
这样的话，我们就很接近快速幂的本质了，我们会发现令：
A1=(a^(bx*2^x)%c)
...
An=(a^(bn*2^n)%c)
这样的话，An 始终是 A(n-1) 的【平方倍】，依次递推。
*/
// 快速模幂
// 朴素的时间复杂度：O(n)
// 快速幂时间复杂度：O(logn)
ll power(ll a,ll b,ll c)
{
ll ans=1; // 记录结果
a=a%c; // 预处理，使得a处于c的数据范围之下
while(b!=0) // ~while(b)
{
if(b&1) ans=ans*a%c; // 如果b的二进制位不是0，那么我们的结果是要参与运算的
else ans=ans*1%c; // b的二进制位是1
b>>=1; // 不断遍历b的二进制位
a=a*a%c; // 不断加倍
}
return ans;
}
