注意

yukicoder contest 279 (Zelkova and Cherry) の問題は 難易度順に並んではいない. よって, 問題文や難易度を表すの星の数, 正解者数等といった公開されている情報から問題を取捨選択することを強く推奨する.

問題文

Yuki君は3つのアイドルグループN道, K道, H道のCDを購入した.それぞれのグループのCDの値段は1枚につき $N$ 円, $K$ 円, $H$ 円であった. Yuki君はこの3つのアイドルグループのCDをそれぞれ何枚かずつ買い,その結果として合計 $Y$ 円になった. このとき,Yuki君が購入したCDの枚数の組み合わせとして可能な場合の数はいくつか?

ただし,解答は非常に大きくなる可能性があるので, $10^9+7$ で割った余りを出力せよ.

また,合計 $Y$ 円になるのであれば, 1枚も購入していないCDがあってもよいとする.

$T$ 個のテストケースについて答えよ.

制約

• $1 \leq T \leq 20$
• $1 \leq N,K,H\leq 10^6$
• $1 \leq Y \leq 10^{12}$
• $\min \left(\left \lfloor \dfrac{Y}{N} \right \rfloor, \left \lfloor \dfrac{Y}{K} \right \rfloor, \left \lfloor \dfrac{Y}{H} \right \rfloor \right) \leq 10^6$
• 入力は全て整数である.

入力

$T$

$N\ K\ H\ Y$

出力

$T$ 行出力せよ. ただし, $i$ 行目には $i$ 番目のテストケースに対する答えを出力せよ. また, それぞれのテストケースについて, 最後に改行を忘れないこと.

サンプル

4
2 3 5 9
4 5 1 1
10 10 10 1
31415 92653 58979 3238462643

3
1
0
30554