题目描述

一辺の長さが $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$ 以下である。

输入格式

入力は以下の形式で標準入力から与えられる。

$A$ $B$ $C$ $D$

输出格式

条件を満たすブロックの個数を $10^9\ +\ 7$ で割った余りを出力せよ。

3 4 5 1

54

1 2 3 0

4

3 5 7 100

105

3 123456781 1000000000 100

444124403

1234 12345 1234567 5

150673016

999999997 999999999 1000000000 50000

8402143

提示

制約

• $1\ \leq\ A\ <\ B\ <\ C\ \leq\ 10^{9}$
• $A,\ B,\ C$ はどの $2$ つも互いに素
• $0\ \leq\ D\ \leq\ 50,000$

Sample Explanation 1

以下の図は、直方体を $xy$ 平面に平行な平面で $5$ 段に分けて描いたものです。 ただし、$i\ -\ 1\ \leq\ z\ \leq\ i$ の範囲に含まれるブロックを $i$ 段目と呼んでいます。 黒く塗ったブロックは針金が通っているブロックであり、これらはすべて条件を満たします。 また、黄色く塗ったブロックはそれら以外で条件を満たすブロックです。  黒または黄色に塗られたブロックは全部で $54$ 個存在します。

Sample Explanation 2

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

Sample Explanation 3

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