Problem Description

A point $ P $ on the $ xy $ plane is called a lattice point if both the $ x $ and $ y $ coordinates of point $ P $ are integers.

For a triangle $ ABC $ on the $ xy $ plane, let the function $ f(ABC) $ be the number of lattice points inside the triangle $ ABC $ (excluding those on the boundary).

You are given eight integers $ X_1 $, $ Y_1 $, $ X_2 $, $ Y_2 $, $ X_3 $, $ Y_3 $, $ W $, and $ H $.

Find the sum of the values of $ f(ABC) $ for all triangles $ ABC $ that satisfy the following conditions, modulo $10^9\ +\ 7$.

• The $ x $ coordinate of vertex $ A $ is an integer between $ X_1 $ and $X_1\ +\ W - 1$ (inclusive), and the $ y $ coordinate is an integer between $ Y_1 $ and $Y_1\ +\ H - 1$ (inclusive).
• The $ x $ coordinate of vertex $ B $ is an integer between $ X_2 $ and $X_2\ +\ W - 1$ (inclusive), and the $ y $ coordinate is an integer between $ Y_2 $ and $Y_2\ +\ H - 1$ (inclusive).
• The $ x $ coordinate of vertex $ C $ is an integer between $ X_3 $ and $X_3\ +\ W - 1$ (inclusive), and the $ y $ coordinate is an integer between $ Y_3 $ and $Y_3\ +\ H - 1$ (inclusive).

Input Format

The input is given from the standard input in the following format:

$ X_1 $ $ Y_1 $ $ X_2 $ $ Y_2 $ $ X_3 $ $ Y_3 $ $ W $ $ H $

Output Format

Output the answer.

Sample Input and Output

Sample Input #1

0 0
4 1
2 3
2 1

Sample Output #1

32

Sample Input #2

1 2
100 50
50 100
10 10

Sample Output #2

669378679

Sample Input #3

100 100
10000 1000
1000 10000
99 101

Sample Output #3

69068642

Sample Input #4

0 0
1000000000000 100000000000
100000000000 1000000000000
1 1

Sample Output #4

24258851

Sample Input #5

83014267509 107013567012
918384543326 586909285896
391608717054 614178832969
40000 40000

Sample Output #5

569338479

Notes/Hints

Constraints

• $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$

Sample Explanation 1

In the figure below, we need to find the sum of $ f(A_iB_jC_k) $ ($i,\ j,\ k\ \in\ \{1,\ 2\}$) modulo $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$

Thus, the answer is the sum of these values modulo $10^9\ +\ 7$, which is $ 32 $.

见题面 Input 部分

见题面 Output 部分