Note

The problems of yukicoder contest 279 (Zelkova and Cherry) are not sorted in order of difficulty. Therefore, you are strongly encouraged to choose which problems to attempt based on publicly available information, such as the problem statements, the number of stars indicating difficulty, and the number of accepted solvers.

Problem Statement

Yuki purchased CDs of three idol groups: N-do, K-do, and H-do. The CDs of these groups cost $N$ yen, $K$ yen, and $H$ yen per copy, respectively. Yuki bought some number of copies of each of these three idol groups' CDs, and as a result the total came to $Y$ yen. How many combinations of numbers of CDs could Yuki have purchased?

Since the answer can be very large, output it modulo $10^9+7$.

Also, as long as the total is $Y$ yen, there may be groups of which no CD was purchased.

Solve $T$ test cases.

Constraints

• $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$
• All input values are integers.

Input

$T$

$N\ K\ H\ Y$

Output

Output $T$ lines. The $i$-th line should contain the answer to the $i$-th test case. Also, do not forget to print a newline at the end for each test case.

Sample

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

3
1
0
30554