#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1505;
const int mod=1e9+7;
int T,n,p,m,k;
int a[N][N],c[N][N],f[N],inv,inv1;
int qpow(int x,int y){
int ans=1;
while(y){
if(y&1) ans=ans*x%mod;
x=x*x%mod;
y>>=1;
}
return ans;
}
void init(){
inv=qpow(m+1,mod-2),inv1=qpow(m,mod-2),f[0]=qpow(m*inv%mod,k);
for(int i=1;i<=min(n+1,k);i++) f[i]=f[i-1]*inv1%mod*qpow(i,mod-2)%mod*(k-i+1)%mod;
}
void gauss(){
for(int i=1;i<=n;i++){
int inv=qpow(a[i][i],mod-2);
a[i][i]=1,a[i][n+1]=a[i][n+1]*inv%mod;
if(i!=n) a[i][i+1]=a[i][i+1]*inv%mod;
for(int j=i+1;j<=n;j++){
int mult=a[j][i];
a[j][i]=0;
if(i!=n) a[j][i+1]=(a[j][i+1]-mult*a[i][i+1]%mod+mod)%mod;
a[j][n+1]=(a[j][n+1]-mult*a[i][n+1]%mod+mod)%mod;
}
}
for(int i=n;i>1;i--){
a[i-1][n+1]=(a[i-1][n+1]-a[i-1][i]*a[i][n+1]%mod+mod)%mod;
a[i-1][i]=0;
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
for(int i=1;i<N;i++){
c[i][0]=1;
for(int j=1;j<=i;j++) c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
}
cin>>T;
while(T--){
memset(a,0,sizeof a),memset(f,0,sizeof f);
cin>>n>>p>>m>>k;
if(k==0){
cout<<"-1\n";
continue;
}
if(m==0){
if(k==1) cout<<"-1\n";
else{
int ans=0,cur=p;
while(cur>0){
if(cur<n) cur++;
cur-=k,ans++;
}
cout<<ans<<"\n";
}
continue;
}
init();
for(int i=1;i<n;i++){
for(int j=1;j<=i;j++) a[i][j]=(f[i-j]*m%mod+f[i-j+1])%mod*inv%mod;
a[i][i+1]=f[0]*inv%mod,a[i][i]=(a[i][i]-1+mod)%mod,a[i][n+1]=mod-1;
}
for(int i=1;i<=n;i++) a[n][i]=f[n-i];
a[n][n]=(a[n][n]-1+mod)%mod,a[n][n+1]=mod-1;
gauss();
cout<<a[p][n+1]<<"\n";
}
return 0;
}
Comments NOTHING