typedef long long LL;
//求a^b%m,递归写法
LL binaryPow(LL a, LL b, LL m)
{
  if (b == 0)return 1;//如果b为0，那么a^0=1
  //b为奇数，转换为b-1
  if (b % 2 == 1)return a*binaryPow(a, b - 1, m) % m;
  else//b为偶数，转换为b/2
  {
    LL mul = binaryPow(a, b / 2, m);
    return mul*mul%m;
  }
}
//迭代写法
LL binaryPow(LL a, LL b, LL m)
{
  LL ans = 1;
  while (b > 0)
  {
    if (b & 1)//如果b的二进制末尾为1(也可以写成if(b%2))
    {
      ans = ans*a%m;
    }
    a = a*a%m;//令a平方
    b >>= 1;//将b的二进制右移一位，即b=b>>1或b=b/2
  }
  return ans;
}