#include<bits/stdc++.h>
#define ll long long
#define int long long
#define R register
using namespace std;
long long a[1505][1505],f[2000005],dp[2000050],m,k,p,T;
long long mod=1e9+7,P=mod;
ll ksm(ll a, ll n)//计算a^n % mod
{
    ll re = 1;
    while(n)
    {
        if(n & 1)//判断n的最后一位是否为1
            re = (re * a) % mod;
        n >>= 1;//舍去n的最后一位
        a = (a * a) % mod;//将a平方
    }
    return re % mod;
}
long long n,d[1000100];
long long inv(ll x){
	return ksm(x,mod-2)%mod;
}
long long ji[1000100];
inline ll dec(R ll x,R ll y){return x-y<0?x-y+P:x-y;}
inline ll mul(R ll x,R ll y){return 1ll*x*y-1ll*x*y/P*P;}
void zyq1152(){
	for(int i=1;i<=n;i++){
	    ll t=inv(a[i][i]);
	    a[i][i]=1;
	    a[i][n+1]=mul(a[i][n+1],t);
	    if(i!=n)a[i][i+1]=mul(a[i][i+1],t);
		for(int j=i+1;j<=n;j++){
			t=a[j][i];a[j][i]=0;
			a[j][i+1]=dec(a[j][i+1],mul(a[i][i+1],t));
			a[j][n+1]=dec(a[j][n+1],mul(a[i][n+1],t));
		}
	}
	dp[n]=a[n][n+1];
//	cout<<dp[n]<<' ';
	for(int i=n-1;i>=0;i--){
		dp[i]=dec(a[i][n+1],mul(dp[i+1],a[i][i+1]));
	}
}
void getf(){
	ll op=ksm(m+1,k);
	ll op2=ksm(m,k);
	ll er=inv(op);
	f[0]=op2*er%mod;
	for(int i=1;i<=min(n,k);i++){
		f[i]=f[i-1]*(k-i+1);
		f[i]%=mod; 
		f[i]*inv(i);
		f[i]%=mod;
		f[i]*=inv(m);
		f[i]%=mod;
	}
	ll ui=inv(m+1);
	ll ty=ui*m;
	ty%=mod;
	for(int i=1;i<n;i++){
	  for(int j=1;j<=i;j++){
	  	ll we  =1ll*f[i-j]*m%mod;
	  	we+=f[i-j+1];
	  	we%=mod;
	  	we*=ui;
	  	we%=mod;
	  	a[i][j]=we%mod;
	  }
	  a[i][i+1]=1ll*f[0]*ui%mod;
	  a[i][i]=1ll*(a[i][i]-1+mod)%mod;
	}
	for(int i=1;i<=n;i++){
		a[i][n+1]=mod-1;
		a[n][i]=f[n-i];
	}
	a[n][n]=(a[n][n]-1+mod)%mod;
}
ll res;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>T;
	ji[0]=1;
	for(int i=1;i<=1e6+10;i++){
		ji[i]=ji[i-1]*i;
		ji[i]%=mod;
	}
	while(T--){
	cin>>n>>p>>m>>k; 
	res=0;
	if(k==0){cout<<-1<<'\n';continue;}//特判一些特殊情况
    if(m==0)
    {
        if(k==1){cout<<-1<<'\n';continue;}
        for(;p>0;){if(p<n){p++;}p-=k;res++;}cout<<res<<'\n';res=0;continue;}
	getf(); 
	zyq1152();
	cout<<dp[p]<<"\n";
	for(int i=0;i<=n+1;i++){
	for(int j=0;j<=n+1;j++)a[i][j]=0;	
	}	
	for(int i=0;i<=n;i++){
		f[i]=0;dp[i]=0;
	}
	}
}
/* 2 
2 1 1 1*/
```cpp