Problem Description

We have built a rectangular prism of dimensions $A \times B \times C$ by stacking $ABC$ cubes, each with side length $1$. Furthermore, we have placed this rectangular prism in the $xyz$ space such that:

• For all $i, j, k$ ($0 \leq i < A, 0 \leq j < B, 0 \leq k < C$), there exists a block with a diagonal connecting points $(i, j, k)$ and $(i + 1, j + 1, k + 1)$, and all its edges are parallel to the coordinate axes.

We call such a block block $(i, j, k)$.

For two blocks $(i_1, j_1, k_1)$ and $(i_2, j_2, k_2)$, we define their distance as max$(|i_1 - i_2|, |j_1 - j_2|, |k_1 - k_2|)$.

Now, we have inserted a very thin wire along the line segment connecting points $(0, 0, 0)$ and $(A, B, C)$. Your task is to find the number of blocks $(x, y, z)$ that satisfy the following condition, modulo $10^9 + 7$:

• There exists a block $(x', y', z')$ through which the wire passes (excluding blocks that only touch the wire at the boundary), and the distance between block $(x, y, z)$ and block $(x', y', z')$ is at most $D$.

Input Format

The input is given from the standard input in the following format:

$A$ $B$ $C$ $D$

Output Format

Output the number of blocks that satisfy the condition, modulo $10^9 + 7$.

Sample Input and Output

Sample Input #1

3 4 5 1

Sample Output #1

54

Sample Input #2

1 2 3 0

Sample Output #2

4

Sample Input #3

3 5 7 100

Sample Output #3

105

Sample Input #4

3 123456781 1000000000 100

Sample Output #4

444124403

Sample Input #5

1234 12345 1234567 5

Sample Output #5

150673016

Sample Input #6

999999997 999999999 1000000000 50000

Sample Output #6

8402143

Notes/Hints

Constraints

• $1 \leq A < B < C \leq 10^9$
• $A, B, C$ are pairwise coprime
• $0 \leq D \leq 50,000$

Sample Explanation 1

The following figure shows the rectangular prism divided into 5 layers by planes parallel to the $xy$ plane. The blocks painted black are those through which the wire passes, and they all satisfy the condition. The blocks painted yellow are those that also satisfy the condition but are not passed through by the wire. There are a total of 54 blocks painted black or yellow.

Sample Explanation 2

There are 4 blocks through which the wire passes, and these are the only ones that satisfy the condition.

Sample Explanation 3

All blocks satisfy the condition.

见题面 Input 部分

见题面 Output 部分