问题描述

在 $xy$ 平面上，点 $P$ 是一个格点，表示点 $P$ 的横坐标和纵坐标都是整数。

对于三角形 $ABC$ 在 $xy$ 平面上，定义函数 $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_1$ 到 $X_1 + W$ 之间（不包括边界），纵坐标在 $Y_1$ 到 $Y_1 + H$ 之间（不包括边界）。
• 顶点 $B$ 的横坐标在 $X_2$ 到 $X_2 + W$ 之间（不包括边界），纵坐标在 $Y_2$ 到 $Y_2 + H$ 之间（不包括边界）。
• 顶点 $C$ 的横坐标在 $X_3$ 到 $X_3 + W$ 之间（不包括边界），纵坐标在 $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

输出

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

输出

669378679

示例 3

输入

100 100
10000 1000
1000 10000
99 101

输出

69068642

示例 4

输入

0 0
1000000000000 100000000000
100000000000 1000000000000
1 1

输出

24258851

示例 5

输入

83014267509 107013567012
918384543326 586909285896
391608717054 614178832969
40000 40000

输出

569338479