题目描述

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$ で割った余りを求めてください。

输入格式

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

$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$ で割った余りを出力せよ。

题目大意

题目大意：

一个人在网格图上旅行，他可以从矩形$(X_1,Y_1)-(X_2,Y_2)$中任意一点$S$开始，再在矩形$(X_3,Y_3)-(X_4,Y_4)$中任意一点$P$午休，最后在矩形$(X_5,Y_5)-(X_6,Y_6)$中任意一点$T$结束旅行

如果旅行者当前在$(x,y)$，那么他下一步只能移动到$(x,y+1)$或$(x+1,y)$

只要点$S,P,T$不同或旅行经过的点集不同即为不同的方案，求有多少种不同的行走方案，答案对 $10^9+7$ 取模。

保证三个矩形一定从左下到右上排列，且矩形不相交。

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

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

提示

制約

• $1\ \leq\ X_1\ \leq\ X_2$
• $1\ \leq\ Y_1\ \leq\ Y_2$

Sample Explanation 1

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