/*
思路：
    思路一：
       1 (a.b)%c = ((a%c)*(b%c))%c
       2 pow(3,10)=pow(pow(3,2),5)=pow(9*3,4)=pow(pow(27,2),2)


*/

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

typedef long long ll;

ll function_Modexpfast ( ll a , ll b , ll c ) {
    a = a % c;
    ll result = 1; //记录a的b次方
    while ( b != 0 ) { //循环操作 b&1
        if ( b % 2 == 1 ) { // 每次对b除以2 奇数时则是result记录时。
            result = (result * a) % c; //奇数时 a的b次方= a*a * a的b－1次方 
        }
        a = (a * a) % c;
        b = b >> 1; //向右移动一位 就是除以2

    }
    cout << result << endl;
    return result;
}

int main()
{
    int n;
    cin >> n;
    for ( int i = 1; i <= n; i++ ) {
        ll a, b, c;
        cin >> a >> b >> c;
        function_Modexpfast(a , b , c);
    }
      

    return 0;
}

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef pair<int,int> aII;  
using ll = long long;
using ULL = unsigned long long;
const int N = 1e6+5;

inline ll qmi(ll a, ll b, ll p) {
    ll res = 1 % p;
    for (; b; b >>= 1) {
        if (b&1) res = res * a % p;
        a = a * a % p; 
    }
    return res;
}

inline void solve() { 
    ll a, b, p;
    cin >> a >> b >> p;
    cout << qmi(a, b, p) << endl;
}
int main() { 
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    //int _ = 1; 
    int _; cin >> _;
    while (_--) solve();
    return 0;
}

// https://dashoj.com/p/97
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll n;

int main() {
	cin >> n;
	for (ll i = 0; i < n; i++) {
		ll a, k, p, result = 1;
		cin >> a >> k >> p;
		a = a % p;
		while (k) {
			if (k % 2) result = (result * a) % p;
			k /= 2;
			a = (a * a) % p;
		}
        cout << result << endl;
	}
	return 0;
}

def quick_pow_mod_iterative(a, b, p):
    result = 1
    base = a % p
    while b > 0:
        if b % 2 == 1:  # b 是奇数
            result = (result * base) % p
        base = (base * base) % p
        b //= 2
    return result

n = int(input())
for _ in range(n):
    a, k, p = map(int, input().split())
    result = quick_pow_mod_iterative(a, k, p)
    print(result)

#include <bits/stdc++.h>

using namespace std;

long long a ,k ,p;
//mypow 只是一个自定义名字
long long myPow( long long a , long long k , long long p) {
long long res=1;
while (k){
	if(k&1)
	res=res*a%p;
	k >>=1;/相当于指数除以2
	a = a*a%p;
}
return res;
}
        


int main(){

int n;
cin >>n;
while (n--) {
	long long a,k ,p;
	cin >>a>>k >>p;
	cout << myPow(a,k,p) << '\n';
}


return 0;

}

拓展: 如果 $k$ 可以为负数, 即 $a^{-|k|}$ (这样写是为了方便看(因为严格来讲k现在是负数)) 那么可以先求 $a^{|k|}$ 然后 返回 $1/a^{|k|}$ (注: 返回值为double), 特判 k 为负数的情况. (可以试试力扣pow(x, y)这题)❤️

#include <iostream>
using namespace std;

using ll = long long;

ll myPow(ll a, ll k, ll p) {
	ll res = 1;
	while (k) {
		if (k & 1)
			res = res * a % p;
		k >>= 1;
		a = a * a % p;
	}
	return res;
}

int main() {
	int n;
	cin >> n;
	while (n--) {
		ll a, k, p;
		cin >> a >> k >> p;
		cout << myPow(a, k, p) << '\n';
	}
	return 0;
}