H - 三角形と格子点

Time Limit: 4 sec / Memory Limit: 256 MB

配点 : 1400

問題文

xy 平面上の点 P が格子点であるとは、点 Px 座標および y 座標がともに整数であることをいいます。

xy 平面上の三角形 ABC について、関数 f(ABC) を三角形 ABC の内部 (周上は含まない) に存在する格子点の個数とします。

8 個の整数 X_1, Y_1, X_2, Y_2, X_3, Y_3 および W, H が与えられます。

以下の条件を満たす三角形 ABC すべてについての f(ABC) の値の和を 10^9 + 7 で割ったあまりを求めてください。

  • 頂点 Ax 座標は X_1 以上 X_1 + W 未満の整数であり、y 座標は Y_1 以上 Y_1 + H 未満の整数である。
  • 頂点 Bx 座標は X_2 以上 X_2 + W 未満の整数であり、y 座標は Y_2 以上 Y_2 + H 未満の整数である。
  • 頂点 Cx 座標は X_3 以上 X_3 + W 未満の整数であり、y 座標は Y_3 以上 Y_3 + H 未満の整数である。

制約

  • 0 \leq X_i, Y_i \leq 10^{12} (1 \leq i \leq 3)
  • 1 \leq W, H \leq 40\,000
  • X_1 + W \leq X_3
  • X_3 + W \leq X_2
  • Y_1 + H \leq Y_2
  • Y_2 + H \leq Y_3

入力

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

X_1 Y_1
X_2 Y_2
X_3 Y_3
W H

出力

答えを出力せよ。


入力例 1

0 0
4 1
2 3
2 1

出力例 1

32

下の図における f(A_iB_jC_k) (i, j, k \in \{1, 2\}) の和を 10^9 + 7 で割ったあまりを求めれば良いことになります。

image for sample 1

  • f(A_1B_1C_1) = 4
  • f(A_1B_1C_2) = 3
  • f(A_1B_2C_1) = 6
  • f(A_1B_2C_2) = 4
  • f(A_2B_1C_1) = 3
  • f(A_2B_1C_2) = 3
  • f(A_2B_2C_1) = 5
  • f(A_2B_2C_2) = 4

より、答えはこれらの和を 10^9 + 7 で割ったあまりである 32 となります。


入力例 2

1 2
100 50
50 100
10 10

出力例 2

669378679

入力例 3

100 100
10000 1000
1000 10000
99 101

出力例 3

69068642

入力例 4

0 0
1000000000000 100000000000
100000000000 1000000000000
1 1

出力例 4

24258851

入力例 5

83014267509 107013567012
918384543326 586909285896
391608717054 614178832969
40000 40000

出力例 5

569338479