[AGC018E] Sightseeing Plan

题目大意： 一个人在网格图上旅行，他可以从矩形$(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$ 取模。 保证三个矩形一定从左下到右上排列，且矩形不相交。

[problemUrl]: https://atcoder.jp/contests/agc018/tasks/agc018_e 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 $ で割った余りを出力せよ。

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 $ 通りになります。