問題文

xy 平面上の点 P が格子点であるとは、点 P の x 座標および 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 で割ったあまりを求めてください。

• 頂点 A の x 座標は X_1 以上 X_1 + W 未満の整数であり、y 座標は Y_1 以上 Y_1 + H 未満の整数である。
• 頂点 B の x 座標は X_2 以上 X_2 + W 未満の整数であり、y 座標は Y_2 以上 Y_2 + H 未満の整数である。
• 頂点 C の x 座標は 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

入力例 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 で割ったあまりを求めれば良いことになります。

• 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