Cubes

[problemUrl]: https://atcoder.jp/contests/code-festival-2017-qualc/tasks/code_festival_2017_qualc_e 一辺の長さが $ 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 $ 段目と呼んでいます。 黒く塗ったブロックは針金が通っているブロックであり、これらはすべて条件を満たします。 また、黄色く塗ったブロックはそれら以外で条件を満たすブロックです。 !\[b3a8ffcd8621b59d4657bfaa9c25a716.png\](https://img.atcoder.jp/code-festival-2017-qualc/b3a8ffcd8621b59d4657bfaa9c25a716.png) 黒または黄色に塗られたブロックは全部で $ 54 $ 個存在します。 ### Sample Explanation 2 針金が通っているブロックは $ 4 $ 個あり、これらだけが条件を満たします。 ### Sample Explanation 3 すべてのブロックが条件を満たします。