#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
#include <cmath>
using namespace std;
int r,c,b,n;
int memo[55][55][11];
int df (int red,int kolona,int leftofn){
    if(leftofn == 1 && red*kolona >= b){
        return 1;
    }
    if(memo[red][kolona][leftofn] != -1){
        return memo[red][kolona][leftofn];
    }
    int res = 0;
    int mod = 1e9+7;
    if(leftofn>1){
        for (int i = 1; i < red; i++) {
            if(i*kolona>= b){
                res +=( +df(red-i,kolona,leftofn-1)*2) % mod;
                res = res%mod;
            }
        }
        for (int i = 1; i < kolona; i++) {
            if(i*red >= b){
                res += (df(red,kolona-i,leftofn-1)*2) % mod;
                res = res%mod;
            }
        }
    }
    return memo[red][kolona][leftofn] = res;
}
int main(){
int t;
cin >> t;
while(t--){
    cin >> r >> c >> b >> n;
    for (int i = 0; i <= 50; i++) {
        for (int j = 0; j <= 50; j++) {
            for (int k = 0; k < 11; k++) {
                memo[i][j][k] = -1;
            }
        }
    }
    cout << df(r,c,n) << endl;
}
}