SMMR-T033: Power Mod

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

typedef long long lli;

int main(){

    int Q;
    scanf("%d", &Q);
    for(int q = 1; q <= Q; ++q){
        int base, exp, mod;
        scanf("%d %d %d", &base, &exp, &mod);
        vector<lli> exponent(30, 0);
        exponent[0] = base % mod;
        for(int i = 1; i <= 29; ++i){
            exponent[i] = (exponent[i - 1] * exponent[i - 1]) % mod;
        }
        lli ans = 1;
        for(int i = 29; i >= 0; --i){
            if(exp - (1 << i) >= 0){
                ans *= exponent[i];
                ans %= mod;
                exp -= (1 << i);
            }
        }
        cout << ans << "\n";
    }

    return 0;
}