#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int mod = 1e9+7;

struct mat {
    int o[2][2];
    mat(){}
    void init() {
        rep(i,0,1) rep(j,0,1) if(i==j) o[i][j]=1;
    }
    void zero() {
        rep(i,0,1) rep(j,0,1) o[i][j]=0;
    }
    mat operator*(const mat&b) {
        mat res;
        res.zero();
        rep(i,0,1) rep(j,0,1) rep(k,0,1) {
            res.o[i][j]=(res.o[i][j]+1ll*o[i][k]*b.o[k][j]%mod)%mod;
        }
        return res;
    }  
};
mat qpow(mat a, int b) {
    mat res;
    res.zero();
    res.init();
    for (; b;b>>=1) {
        if(b&1) res=res*a;
        a=a*a;
    }
    return res;
}
int qpow(int a, int b) {
    int res=1;
    for(;b;b>>=1) {
        if(b&1) res=1ll*res*a%mod;
        a=1ll*a*a%mod;
    }
    return res;
}
mat a,b;
int n,k,p;
void solve() {
    cin>>n>>k>>p;
    b.o[0][0]=p-2;
    b.o[0][1]=p-1;
    b.o[1][0]=1;
    b.o[1][1]=0;
    a.o[0][0]=0;
    a.o[1][0]=p;
    // rep(i,0,1) rep(j,0,1) cout<<b.o[i][j]<<" \n"[j==1];
    auto res = qpow(b,k-1)*a;
    // rep(i,0,1) rep(j,0,1) cout<<res.o[i][j]<<" \n"[j==1];
    // cout<<res.o[0][0]<<"\n";
    int ans=res.o[0][0];
    int tp=((1ll*p*(p-1)%mod-2ll*p+3)%mod+mod)%mod;
    int mi=1ll*k*(n-1)%(mod-1);
    ans=1ll*ans*qpow(tp,mi)%mod;
    cout<<ans<<"\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--) solve();
}
/*
1
2 3 3
*/