/ 
Time Limit: 2 sec / Memory Limit: 256 MB
配点: 1600 点
問題文
一辺の長さが 1 の立方体の形をしたブロックを ABC 個積み上げて A \times B \times C の直方体を作りました。 さらに、この直方体を以下の条件を満たすように xyz 空間内に配置しました。
- すべての i, j, k (0 \leq i < A, 0 \leq j < B, 0 \leq k < C) に対して、 点 (i, j, k) と点 (i + 1, j + 1, k + 1) を結ぶ線分を対角線として持ち、すべての辺が座標軸と平行なブロックが存在する。
各 i, j, k に対して、上のようなブロックをブロック (i, j, k) と呼ぶことにします。
2 つのブロック (i_1, j_1, k_1) と (i_2, j_2, k_2) に対して、これらの距離を max(|i_1 - i_2|, |j_1 - j_2|, |k_1 - k_2|) と定義します。
いま、点 (0, 0, 0) と点 (A, B, C) を結ぶ線分に沿って、直方体に十分細い針金を通しました。 このとき、以下の条件を満たすブロック (x, y, z) の個数を 10^9 + 7 で割った余りを求めてください。
- ある針金が通っている（境界で接する場合は除く）ブロック (x', y', z') が存在して、ブロック (x, y, z) とブロック (x', y', z') の距離は D 以下である。
制約
- 1 \leq A < B < C \leq 10^{9}
- A, B, C はどの 2 つも互いに素
- 0 \leq D \leq 50,000
入力
入力は以下の形式で標準入力から与えられる。
A B C D
出力
条件を満たすブロックの個数を 10^9 + 7 で割った余りを出力せよ。
入力例 1
3 4 5 1
出力例 1
54
以下の図は、直方体を xy 平面に平行な平面で 5 段に分けて描いたものです。 ただし、i - 1 \leq z \leq i の範囲に含まれるブロックを i 段目と呼んでいます。
黒く塗ったブロックは針金が通っているブロックであり、これらはすべて条件を満たします。 また、黄色く塗ったブロックはそれら以外で条件を満たすブロックです。
黒または黄色に塗られたブロックは全部で 54 個存在します。
入力例 2
1 2 3 0
出力例 2
4
針金が通っているブロックは 4 個あり、これらだけが条件を満たします。
入力例 3
3 5 7 100
出力例 3
105
すべてのブロックが条件を満たします。
入力例 4
3 123456781 1000000000 100
出力例 4
444124403
入力例 5
1234 12345 1234567 5
出力例 5
150673016
入力例 6
999999997 999999999 1000000000 50000
出力例 6
8402143
Score : 1600 points
Problem Statement
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.
Sample Input 1
3 4 5 1
Sample Output 1
54
The figure below shows the parallelepiped, sliced into five layers by planes parallel to xy-plane. Here, the layer in the region i - 1 \leq z \leq i is called layer i.
The blocks painted black are penetrated by the wire, and satisfy the condition. The other blocks that satisfy the condition are painted yellow.
There are 54 blocks that are painted black or yellow.
Sample Input 2
1 2 3 0
Sample Output 2
4
There are four blocks that are penetrated by the wire, and only these blocks satisfy the condition.
Sample Input 3
3 5 7 100
Sample Output 3
105
All blocks satisfy the condition.
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