Binary Exponentiation Template

constexpr int kMod = 1000'000'007;

using ll = int64_t;
  
inline ll Modular(ll num, bool modular) {
  return modular ? num % kMod : num;
}

ll FastPow(ll num, ll exponent, bool modular) {
  ll res = 1;
  ll base = Modular(num, modular);
  while (exponent > 1) {
    if ((exponent & 1) == 1) {
      res = Modular(res * base, modular);
    }
    base = Modular(base * base, modular);
    exponent >>= 1;
  }
  return Modular(res * base, modular);
}

ll FastPowRecursion(ll num, ll exponent, bool modular) {
  if (exponent == 0) {
    return 1;
  }
  if (exponent == 1) {
    return Modular(num, modular);
  }
  // without the following line, num * num might overflow
  num = Modular(num, modular);
  return Modular(((exponent % 2 == 0) ? 1 : num) * FastPowRecursion(num * num, exponent / 2, modular), modular);
}

The recursion version is not slower than the while loop version when it is o2 optimized or above. See https://godbolt.org/z/E9jYefrKG.