T156T3

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)
#define ll long long

template<typename T>
inline void read(T&x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

const int N=5007;
const int p=1e9+7;

inline int sub(int a,int b){
    return (a-=b)<0?a+p:a;
}

inline int add(int a,int b){
    return (a+=b)>=p?a-p:a;
}

inline ll qpow(ll a,ll b){
    ll ans=1;
    while(b){
        if(b&1)(ans*=a)%=p;
        (a*=a)%=p;
        b>>=1;
    }
    return ans;
}

ll r,Inv;

int pre[N];
int suf[N];
int inv[N];
int F[N];

inline ll f(ll x,int n){
    if(x<=n)return F[x];
    x%=p;
    pre[0]=1;
    for(int i=1;i<=n;++i){
        pre[i]=(ll)pre[i-1]*sub(x,i)%p;
    }
    suf[n+1]=1;
    for(int i=n;i>=1;--i){
        suf[i]=(ll)suf[i+1]*sub(x,i)%p;
    }
    ll ret=0;
    for(int i=1;i<=n;++i){
        ret+=((i^n)&1?-1:1)*(ll)F[i]*pre[i-1]%p*suf[i+1]%p*inv[i-1]%p*inv[n-i]%p;
    }
    return (ret%p+p)%p;
}

inline void work(int n){
    for(int i=1;i<n;++i){
        F[i]=sub(F[i+1],F[i]);
    }
}

int solve(ll n,int k){
    if(!n||!k)return 0;
    int ret=sub(f(n%p,k)*qpow(r,(n+1)%(p-1))%p,f(1,k)*r%p);
    work(k);
    return sub(ret,r*solve(n-1,k-1)%p)*Inv%p;
}

ll k,n;

int main(){
    freopen("sword.in","r",stdin);
    freopen("sword.out","w",stdout);
    inv[1]=1;
    for(int i=2;i<N;++i)inv[i]=(ll)(p-p/i)*inv[p%i]%p;
    inv[0]=1;
    for(int i=1;i<N;++i)inv[i]=(ll)inv[i]*inv[i-1]%p;
    int T;r(T);
    while(T--){
        r(k),r(n),r(r);
        r%=p;
        Inv=qpow((r-1)%p,p-2);
        for(int i=1;i<=k+1;++i){
            F[i]=qpow(i,k);
        }
        printf("%d\n",solve(n,k+1));
    }
}