問題文
一辺の長さが 1 の立方体の形をしたブロックを ABC 個積み上げて AtimesBtimesC の直方体を作りました。 さらに、この直方体を以下の条件を満たすように xyz 空間内に配置しました。
- すべての i,j,k (0leqi<A,0leqj<B,0leqk<C) に対して、 点 (i,j,k) と点 (i+1,j+1,k+1) を結ぶ線分を対角線として持ち、すべての辺が座標軸と平行なブロックが存在する。
各 i,j,k に対して、上のようなブロックをブロック (i,j,k) と呼ぶことにします。
2 つのブロック (i1,j1,k1) と (i2,j2,k2) に対して、これらの距離を max(∣i1−i2∣,∣j1−j2∣,∣k1−k2∣) と定義します。
いま、点 (0,0,0) と点 (A,B,C) を結ぶ線分に沿って、直方体に十分細い針金を通しました。 このとき、以下の条件を満たすブロック (x,y,z) の個数を 109+7 で割った余りを求めてください。
- ある針金が通っている(境界で接する場合は除く)ブロック (x′,y′,z′) が存在して、ブロック (x,y,z) とブロック (x′,y′,z′) の距離は D 以下である。
制約
- 1leqA<B<Cleq109
- A,B,C はどの 2 つも互いに素
- 0leqDleq50,000
入力
入力は以下の形式で標準入力から与えられる。
A B C D
出力
条件を満たすブロックの個数を 109+7 で割った余りを出力せよ。
入力例 1
出力例 1
以下の図は、直方体を xy 平面に平行な平面で 5 段に分けて描いたものです。 ただし、i−1leqzleqi の範囲に含まれるブロックを i 段目と呼んでいます。
黒く塗ったブロックは針金が通っているブロックであり、これらはすべて条件を満たします。 また、黄色く塗ったブロックはそれら以外で条件を満たすブロックです。

黒または黄色に塗られたブロックは全部で 54 個存在します。
入力例 2
出力例 2
針金が通っているブロックは 4 個あり、これらだけが条件を満たします。
入力例 3
出力例 3
すべてのブロックが条件を満たします。
入力例 4
出力例 4
入力例 5
出力例 5
入力例 6
出力例 6