#include<bits/stdc++.h>
#define ull unsigned long long
#define ll int64_t
#define f(i,s,e) for(i=s;i<e;++i)
#define endl << "\n"
#define sp << " "
#define INF INFINITY
#define mset(a,b) memset(a,b,sizeof(a))
#define mod 1000000007
#define mp(a,b) make_pair(a,b)
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define crap ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define PI 3.14159265358979323846264338327950288419716939937510
#define pb(a) push_back(a)
#define pf(a) push_front(a)
using namespace std;
ll fpower(ll x,ll y)
{
if(!y)
return 1;
x %= mod;
return (y&1) ? x*fpower(x*x%mod,y/2)%mod : fpower(x*x%mod,y/2)%mod ;
}
ll fpower1(ll a,ll b,ll c)
{
if(!c)
return a%mod;
if(c==1)
return fpower(a,b) ;
return (c&1) ? fpower1(fpower1(a,b,c/2),b,(c/2) + 1)%mod : fpower1(fpower1(a,b,c/2),b,c/2)%mod ;
}
int main()
{
// crap;
int t;
cin>>t;
while(t--)
{
ll i,j,k,n,a,b,c;
cin >> a >> b >> c;
cout << fpower1(a,b,c) endl ;
}
return 0;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KI2RlZmluZSB1bGwgdW5zaWduZWQgbG9uZyBsb25nCiNkZWZpbmUgbGwgaW50NjRfdCAKI2RlZmluZSBmKGkscyxlKSBmb3IoaT1zO2k8ZTsrK2kpCiNkZWZpbmUgZW5kbCA8PCAiXG4iCiNkZWZpbmUgc3AgPDwgIiAiCiNkZWZpbmUgSU5GIElORklOSVRZCiNkZWZpbmUgbXNldChhLGIpIG1lbXNldChhLGIsc2l6ZW9mKGEpKQojZGVmaW5lIG1vZCAxMDAwMDAwMDA3CiNkZWZpbmUgbXAoYSxiKSBtYWtlX3BhaXIoYSxiKQojZGVmaW5lIEYgZmlyc3QKI2RlZmluZSBTIHNlY29uZAojZGVmaW5lIGFsbCh4KSB4LmJlZ2luKCkseC5lbmQoKQojZGVmaW5lIGNyYXAgaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbyhmYWxzZSk7IGNpbi50aWUoTlVMTCk7IGNvdXQudGllKE5VTEwpCiNkZWZpbmUgUEkgMy4xNDE1OTI2NTM1ODk3OTMyMzg0NjI2NDMzODMyNzk1MDI4ODQxOTcxNjkzOTkzNzUxMAojZGVmaW5lIHBiKGEpIHB1c2hfYmFjayhhKQojZGVmaW5lIHBmKGEpIHB1c2hfZnJvbnQoYSkKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmxsIGZwb3dlcihsbCB4LGxsIHkpCnsKCWlmKCF5KQoJCXJldHVybiAxOwoJeCAlPSBtb2Q7CglyZXR1cm4gKHkmMSkgPyB4KmZwb3dlcih4KnglbW9kLHkvMiklbW9kIDogZnBvd2VyKHgqeCVtb2QseS8yKSVtb2QgOwp9CgpsbCBmcG93ZXIxKGxsIGEsbGwgYixsbCBjKQp7CglpZighYykKCQlyZXR1cm4gYSVtb2Q7CglpZihjPT0xKQoJCXJldHVybiBmcG93ZXIoYSxiKSA7CglyZXR1cm4gKGMmMSkgPyBmcG93ZXIxKGZwb3dlcjEoYSxiLGMvMiksYiwoYy8yKSArIDEpJW1vZCAgOiBmcG93ZXIxKGZwb3dlcjEoYSxiLGMvMiksYixjLzIpJW1vZCA7CQkKfQoKCmludCBtYWluKCkKewovLwljcmFwOwoJaW50IHQ7CgljaW4+PnQ7Cgl3aGlsZSh0LS0pCgl7CgkJbGwgaSxqLGssbixhLGIsYzsKCQljaW4gPj4gYSA+PiBiID4+IGM7CgkJY291dCA8PCBmcG93ZXIxKGEsYixjKSBlbmRsIDsKCX0KCXJldHVybiAwOwp9