题目描述

我们构造了一个边长为 $A \times B \times C$ 的长方体，由 $ABC$ 个边长为 $1$ 的立方体块组成。然后，我们按照以下方式将长方体放置在三维坐标空间中：

• 对于每个三元组 $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 50000$

---

输入

输入从标准输入中按以下格式给出：

$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