Modular binary exponentation

powMod.cpp

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll powMod(ll a, ll b, ll m) {
    if (b == 0) {
        return 1;
    }

    ll x = powMod(a, b / 2, m) % m;

    if (b % 2) {
        return ((x * x) % m * a) % m;
    } else {
        return (x * x) % m;
    }
}

int main() {
    ios::sync_with_stdio(0);
    cout.tie(0);
    cin.tie(0);

    ll t;
    cin >> t;

    while (t--) {
        ll a, b;
        cin >> a >> b;

        cout << powMod(a, b, 1e9 + 7) << '\n';
    }
}