#include<bits/stdc++.h>
using namespace std;
#define endl “\n”
#define sd(val) scanf("%d",&val)
#define ss(val) scanf("%s",&val)
#define sl(val) scanf("%lld",&val)
#define all(v) v.begin(),v.end()
#define PB push_back
#define MP make_pair
#define FF first
#define SS second
#define ll long long int
#define MOD 1000000007
#define clr(val) memset(val,0,sizeof(val))
#define FIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int multiply(ll x, ll y, ll p)
{
ll res = 1; // Initialize result
while (y > 0)
{
// If y is odd, multiply x with result
if (y & 1)
res = (res*x)%p;
// y must be even now
y = y>>1; // y = y/2
x = (x*x)%p; // Change x to x^2
}
return res;
}
int main()
{
int t;
cin>>t;
while(t–)
{
ll a,n,p;
cin>>a>>n>>p;ll ans=1;
for(int i=1;i<=n;i++)
{
ans=(ans*(multiply(a,i,p)))%p;
}
cout<<ans<<endl;
}
return 0;
}
