#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;

const int MOD = 10007;

// Function to calculate the number of valid matrices
int countValidMatrices(int N, int M, int P, int K) {
    vector<vector<int>> dp(N + 1, vector<int>(M + 1, 0));
    dp[0][0] = 1;

    // Iterate over each cell of the matrix
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            for (int k = 1; k <= K * P; ++k) {
                if (k % K == 0) {
                    dp[i + 1][j + 1] = (dp[i + 1][j + 1] + dp[i][j]) % MOD;
                }
            }
        }
    }

    return dp[N][M];
}

int main() {
    // Open input and output files
    freopen("matrice5.in", "r", stdin);
    freopen("matrice5.out", "w", stdout);

    int T;
    cin >> T;

    while (T--) {
        int N, M, P, K;
        cin >> N >> M >> P >> K;

        int result = countValidMatrices(N, M, P, K);
        cout << result << endl;
    }

    return 0;
}