#codefestival2017qualce. [code_festival_2017_qualc_e]Cubes
[code_festival_2017_qualc_e]Cubes
問題文
一辺の長さが の立方体の形をしたブロックを 個積み上げて の直方体を作りました。 さらに、この直方体を以下の条件を満たすように 空間内に配置しました。
- すべての () に対して、 点 と点 を結ぶ線分を対角線として持ち、すべての辺が座標軸と平行なブロックが存在する。
各 に対して、上のようなブロックをブロック と呼ぶことにします。
つのブロック と に対して、これらの距離を max と定義します。
いま、点 と点 を結ぶ線分に沿って、直方体に十分細い針金を通しました。 このとき、以下の条件を満たすブロック の個数を で割った余りを求めてください。
- ある針金が通っている(境界で接する場合は除く)ブロック が存在して、ブロック とブロック の距離は 以下である。
制約
- はどの つも互いに素
入力
入力は以下の形式で標準入力から与えられる。
出力
条件を満たすブロックの個数を で割った余りを出力せよ。
入力例 1
3 4 5 1
出力例 1
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