#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb emplace_back
#define ii pair<int, int>
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define sz(s) (int)((s).size())
#define all(a) a.begin(), a.end()
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define F0R(i, b) for (int i = 0, _b = (b); i < _b; ++i)
#define FORd(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define F0Rd(i, b) for (int i = (b)-1; i >= 0; i--)
using namespace std;

template<typename T1, typename T2> bool ckmax(T1 &A, const T2 &B){if(A < B){A = B;return true;} return false;}
template<typename T1, typename T2> bool ckmin(T1 &A, const T2 &B){if(A > B){A = B;return true;} return false;}

const int MOD = (int)1234567891; // 998244353
const int N = 123 + 10, M = 18;
const int INF = (int)2e9 + 11;
const long long LINF = (long long)4e18 + 11;

/*
     /\_/\
    (= ._.)
    / >?  \>$
*/

#define int long long
int pref[N], suf[N];
int F[N], IF[N];
int f[N];

int Pow(int a, int b){
    int res = 1;
    for(; b > 0; b >>= 1, a = 1LL * a * a % MOD) if(b & 1) res = 1LL * res * a % MOD;
    return res;
}

int S(int k, long long m){
    int n = k+1;
    pref[0] = m;
    FOR(i, 1, n) pref[i] = 1LL * pref[i-1] * (m-i) % MOD;
    suf[n] = m-n;
    F0Rd(i, n) suf[i] = 1LL * suf[i+1] * (m-i) % MOD;

    int res = 0, fi = 0;
    for(int i = 0; i <= n; i++){
        fi = (fi + Pow(i, k) * (i > 0)) % MOD;
//        cout << i << ' ' << fi << ' ' << Pow(i, k) << '\n';
        int num = 1LL * (i == 0 ? 1 : pref[i-1]) * (i == n ? 1 : suf[i+1]) % MOD;
        int dem = 1LL * IF[i] * IF[n-i] % MOD;
        if((n-i) & 1) num = (MOD - num) % MOD;
        (res += (1LL * fi * num % MOD * dem % MOD + MOD) % MOD) %= MOD;
        if(res < 0) res += MOD;
    }
    return res;
}

int T(int k, long long m){
    int res = 1LL * (m+1) * S(k, m) % MOD;
    res = (res + (MOD - S(k+1, m)) % MOD) % MOD;
    return res;
}

// code chưa xử lí tràn số khi m > 2*10^9
void sol(void){
    int k, a, m, d; cin >> k >> a >> m >> d;
    int n = k+3;
    F[0] = 1;
    FOR(i, 1, n) F[i] = 1LL * F[i-1] * i % MOD;
    IF[n] = Pow(F[n], MOD-2);
    F0Rd(i, n) IF[i] = 1LL * IF[i+1] * (i+1) % MOD;

    // fi
    f[0] = T(k, a);
    FOR(i, 1, n) f[i] = (f[i-1] + T(k, a+i*d)) % MOD;

    // pref, suf
    pref[0] = m;
    FOR(i, 1, n) pref[i] = 1LL * pref[i-1] * (m-i) % MOD;
    suf[n] = m-n;
    F0Rd(i, n) suf[i] = 1LL * suf[i+1] * (m-i) % MOD;

    // f(x)
    int res = 0;
    for(int i = 0; i <= n; i++){
        int num = 1LL * (i == 0 ? 1 : pref[i-1]) * (i == n ? 1 : suf[i+1]) % MOD;
        int dem = 1LL * IF[i] * IF[n-i] % MOD;
        if((n-i) & 1) num = (MOD - num) % MOD;
        (res += (1LL * f[i] * num % MOD * dem % MOD + MOD) % MOD) %= MOD;
        if(res < 0) res += MOD;
    }
    cout << res << '\n';
}

signed main(void){
    #define TASK "nhap"
    if(fopen(TASK".inp", "r")){
        freopen(TASK".inp", "r", stdin);
        freopen(TASK".out", "w", stdout);
    }
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int t = 1;
    cin >> t;
    while(t--) sol();
    cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << " ms\n";
}