#include #define rep(i, n) for(int(i) = 0; (i) < (n); (i)++) #define FOR(i, m, n) for(int(i) = (m); (i) < (n); (i)++) #define ALL(v) (v).begin(), (v).end() #define LLA(v) (v).rbegin(), (v).rend() #define SZ(v) (v).size() #define INT(...) \ int __VA_ARGS__; \ read(__VA_ARGS__) #define LL(...) \ ll __VA_ARGS__; \ read(__VA_ARGS__) #define DOUBLE(...) \ double __VA_ARGS__; \ read(__VA_ARGS__) #define CHAR(...) \ char __VA_ARGS__; \ read(__VA_ARGS__) #define STRING(...) \ string __VA_ARGS__; \ read(__VA_ARGS__) #define VEC(type, name, size) \ vector name(size); \ read(name) using namespace std; using ll = long long; using pii = pair; using pll = pair; using Graph = vector>; template struct edge { int to; T cost; edge(int t, T c) : to(t), cost(c) {} }; template using WGraph = vector>>; const int INF = 1 << 30; const ll LINF = 1LL << 60; const int MOD = 1e9 + 7; template inline vector make_vec(size_t a, T val) { return vector(a, val); } template inline auto make_vec(size_t a, Ts... ts) { return vector(a, make_vec(ts...)); } void read() {} template inline void read(T &a) { cin >> a; } template inline void read(pair &p) { read(p.first), read(p.second); } template inline void read(vector &v) { for(auto &a : v) read(a); } template inline void read(Head &head, Tail &...tail) { read(head), read(tail...); } template inline void chmax(T &a, T &b) { (a < b ? a = b : a); } template inline void chmin(T &a, T &b) { (a > b ? a = b : a); } ll extgcd(ll a, ll b, ll &x, ll &y) { if(b == 0) { x = 1; y = 0; return a; } ll d = extgcd(b, a % b, y, x); y -= a / b * x; return d; } ll floor_div(ll a, ll b) { assert(b != 0); if(b < 0) a = -a, b = -b; return a >= 0 ? a / b : (a - (b - 1)) / b; } ll ceil_div(ll a, ll b) { assert(b != 0); if(b < 0) a = -a, b = -b; return a >= 0 ? (a + b - 1) / b : a / b; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); INT(t); while(t--) { VEC(ll, a, 3); LL(y); sort(LLA(a)); ll n = a[0], k = a[1], h = a[2]; ll res = 0; ll g = __gcd(k, h); k /= g, h /= g; for(int i = 0; i <= y / n; i++) { ll s = y - n * i; ll p, q; if(s % g != 0) continue; s /= g; extgcd(k, h, p, q); res += max(0LL, floor_div(s * q, k) - ceil_div(-s * p, h) + 1); res %= MOD; } cout << res << endl; } }