分数: 1600 点
问题陈述
我们构造了一个长方体的尺寸 A \times B \times C 建成 ABC 侧面立方块 1。 然后,我们将平行六面体放入 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).
对于两个块 (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) 和 (x', y', z') 最多是 D.
约束
- 1 \leq A < B < C \leq 10^{9}
- 三个整数中的任意两个 A, B 和 C 互质。
- 0 \leq D \leq 50,000
输入
输入由标准输入按以下格式给出:
A B C D
输出
打印满足条件的块的数量,模 10^9 + 7.
示例输入 1
3 4 5 1
示例输出 1
54
下图显示了平行六面体,被平行于 xy- 平面。 这里,区域中的层 i - 1 \leq z \leq i 称为图层 i.
漆成黑色的方块被电线穿透,并且满足条件。 满足条件的其他块被涂成黄色。
有 54 被涂成黑色或黄色的方块。
示例输入 2
1 2 3 0
示例输出 2
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