配点 : $1600$ 点

問題文

joisinoお姉ちゃんは、高橋町を観光する計画を立てています。 高橋町は、正方形の区画が東西南北に敷き詰められた形をしており、 西から $x$ 番目、北から $y$ 番目の区画を区画 $(x,y)$ と呼ぶことにします。

joisinoお姉ちゃんは、以下の条件を満たす観光計画を、よい観光計画だと思っています。

• 観光を始める区画を区画 $(p,q)$ としたときに、$X_1 \leq p \leq X_2$ , $Y_1 \leq q \leq Y_2$ を満たしている。
• お昼ごはんを食べる区画を区画 $(s,t)$ としたときに、$X_3 \leq s \leq X_4$ , $Y_3 \leq t \leq Y_4$ を満たしている。
• 観光を終了する区画を区画 $(u,v)$ としたときに、$X_5 \leq u \leq X_6$ , $Y_5 \leq v \leq Y_6$ を満たしている。
• 観光の開始地点から終了地点まで、お昼ごはんを食べる区画を通りながら、隣接する(辺を共有する)区画への移動を繰り返して、最短距離で移動している。

ある二つの観光計画は、観光を開始する区画、お昼ご飯を食べる区画、観光を終了する区画、または途中で訪れる区画が異なる時、異なる観光計画とみなされます。 joisinoお姉ちゃんは、よい観光計画が何通りあるかを知りたくなりました。 よい観光計画が何通りあるかを求めてください。 なお、答えは非常に大きくなることがあるので、$10^9+7$ で割った余りを求めてください。

制約

• $1 \leq X_1 \leq X_2 < X_3 \leq X_4 < X_5 \leq X_6 \leq 10^6$
• $1 \leq Y_1 \leq Y_2 < Y_3 \leq Y_4 < Y_5 \leq Y_6 \leq 10^6$

入力

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

$X_1$ $X_2$ $X_3$ $X_4$ $X_5$ $X_6$

$Y_1$ $Y_2$ $Y_3$ $Y_4$ $Y_5$ $Y_6$

出力

よい観光計画が何通りあるかを求め、その値を $10^9+7$ で割った余りを出力せよ。

1 1 2 2 3 4
1 1 2 2 3 3

10

観光を開始する区画は必ず区画 $(1,1)$ に、お昼ご飯を食べる区画は必ず区画 $(2,2)$ になります。 観光を終了する区画が区画　$(3,3)$ のとき、移動する方法は $4$ 通りあります。 観光を終了する区画が区画　$(4,3)$ のとき、移動する方法は $6$ 通りあります。 よって、この例の答えは $6+4=10$ 通りになります。

1 2 3 4 5 6
1 2 3 4 5 6

2346

77523 89555 420588 604360 845669 973451
2743 188053 544330 647651 709337 988194

137477680