AT_agc018_e [AGC018E] Sightseeing Plan

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

N/A

N/A

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