// #include using namespace std; #define fi first #define se second #define all(x) x.begin(), x.end() #define lch (o << 1) #define rch (o << 1 | 1) typedef double db; typedef long long ll; typedef unsigned int ui; typedef pair pint; typedef tuple tint; const int MOD = 1e9 + 7; const int INF = 0x3f3f3f3f; const ll INF_LL = 0x3f3f3f3f3f3f3f3f; // Cal(a, b, c, n) = sum[i = 1 -> n]: floor((a * i + b) / c) ll euclidean(ll a, ll b, ll c, ll n) { if (a == 0) return b / c * (n + 1) % MOD; if (a >= c || b >= c) return (n * (n + 1) / 2 % MOD * (a / c) % MOD + (n + 1) * (b / c) % MOD + euclidean(a % c, b % c, c, n)) % MOD; ll m = (a * n + b) / c; return (n * m % MOD - euclidean(c, c - b - 1, a, m - 1)) % MOD; } ll cal(ll a, ll b, ll p) { ll xmax = p / a; ll x0 = p - a * xmax; ll ret = x0 / b + euclidean(a, x0, b, xmax) + (xmax + 1); return ret; } void solve() { ll a, b, c, s; cin >> a >> b >> c >> s; if (s / a < s / c) swap(a, c); if (s / b < s / c) swap(b, c); ll sum = 0; ll zUpp = s / c; for (ll z = 0; z <= zUpp; z++) { ll p = s - z * c; if (p == 0) sum++; else if (p > 0) sum += cal(a, b, p) - cal(a, b, p - 1); } cout << sum % MOD << endl; } int main() { ios::sync_with_stdio(0); int t; cin >> t; while (t--) solve(); return 0; }