配点: $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$ で割った余りを出力せよ。

3 4 5 1

54

以下の図は、直方体を $xy$ 平面に平行な平面で $5$ 段に分けて描いたものです。 ただし、$i - 1 \leq z \leq i$ の範囲に含まれるブロックを $i$ 段目と呼んでいます。

黒く塗ったブロックは針金が通っているブロックであり、これらはすべて条件を満たします。 また、黄色く塗ったブロックはそれら以外で条件を満たすブロックです。

黒または黄色に塗られたブロックは全部で $54$ 個存在します。

1 2 3 0

4

針金が通っているブロックは $4$ 個あり、これらだけが条件を満たします。

3 5 7 100

105

すべてのブロックが条件を満たします。

3 123456781 1000000000 100

444124403

1234 12345 1234567 5

150673016

999999997 999999999 1000000000 50000

8402143