#D12487. Cubes
Cubes
Cubes
We constructed a rectangular parallelepiped of dimensions A \times B \times C built of ABC cubic blocks of side 1. Then, we placed the parallelepiped in xyz-space as follows:
- For every triple i, j, k (0 \leq i < A, 0 \leq j < B, 0 \leq k < C), there exists a block that has a diagonal connecting the points (i, j, k) and (i + 1, j + 1, k + 1). All sides of the block are parallel to a coordinate axis.
For each triple i, j, k, we will call the above block as block (i, j, k).
For two blocks (i_1, j_1, k_1) and (i_2, j_2, k_2), we will define the distance between them as max(|i_1 - i_2|, |j_1 - j_2|, |k_1 - k_2|).
We have passed a wire with a negligible thickness through a segment connecting the points (0, 0, 0) and (A, B, C). How many blocks (x,y,z) satisfy the following condition? Find the count modulo 10^9 + 7.
- There exists a block (x', y', z') such that the wire passes inside the block (x', y', z') (not just boundary) and the distance between the blocks (x, y, z) and (x', y', z') is at most D.
Constraints
- 1 \leq A < B < C \leq 10^{9}
- Any two of the three integers A, B and C are coprime.
- 0 \leq D \leq 50,000
Input
Input is given from Standard Input in the following format:
A B C D
Output
Print the number of the blocks that satisfy the condition, modulo 10^9 + 7.
Examples
Input
3 4 5 1
Output
54
Input
1 2 3 0
Output
4
Input
3 5 7 100
Output
105
Input
3 123456781 1000000000 100
Output
444124403
Input
1234 12345 1234567 5
Output
150673016
Input
999999997 999999999 1000000000 50000
Output
8402143
inputFormat
Input
Input is given from Standard Input in the following format:
A B C D
outputFormat
Output
Print the number of the blocks that satisfy the condition, modulo 10^9 + 7.
Examples
Input
3 4 5 1
Output
54
Input
1 2 3 0
Output
4
Input
3 5 7 100
Output
105
Input
3 123456781 1000000000 100
Output
444124403
Input
1234 12345 1234567 5
Output
150673016
Input
999999997 999999999 1000000000 50000
Output
8402143
样例
1 2 3 04