#include <bits/stdc++.h>
#define ll long long

using namespace std;

ll mul(ll a, ll b, ll MOD = 1e9 + 7) {
    return ((a % MOD) * (b % MOD)) % MOD;
}

ll add(ll a, ll b, ll MOD = 1e9 + 7) {
     return ((a % MOD) + (b % MOD)) % MOD;
}

ll sub(ll a, ll b, ll MOD = 1e9 + 7) {
     return (((a - b) % MOD) + MOD) % MOD;
}

int main() {
    ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    ll MOD = 1e9+7;
    int t;
    cin >> t;
    while (t--) {
        ll a,b,c,n;
        cin >> a >> b >> c >> n;
        multiset<ll>s;
        ll ans=0;
        ans++;
        s.insert(1);
        for (int i=2; i<=n; i++) {
            ll x=add(add(mul(a,*next(s.begin(),(s.size()-1)/2)),mul(b,i)),c)%MOD;
            ans+=x;
            ans%=MOD;
            s.insert(x);
        }
        cout << ans%MOD << endl;

    }
    return 0;
}

/*
 * 3 1 2 6
 * 1 2 3 4 5 6
 * 1 7 8
 */