E - Sightseeing Plan

Contest Duration: 2017-07-23(Sun) 12:00 - 2017-07-23(Sun) 14:10 (local time) (130 minutes) Back to Home

E - Sightseeing Plan Editorial

Time Limit: 8 sec / Memory Limit: 256 MiB

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

入力例 1Copy

Copy

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

出力例 1Copy

Copy

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

入力例 2Copy

Copy

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

出力例 2Copy

Copy

入力例 3Copy

Copy

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

出力例 3Copy

Copy

137477680

Score : $1600$ points

Problem Statement

Joisino is planning on touring Takahashi Town. The town is divided into square sections by north-south and east-west lines. We will refer to the section that is the $x$ -th from the west and the $y$ -th from the north as $(x,y)$ .

Joisino thinks that a touring plan is good if it satisfies the following conditions:

Let $(p,q)$ be the section where she starts the tour. Then, $X_1 \leq p \leq X_2$ and $Y_1 \leq q \leq Y_2$ hold.
Let $(s,t)$ be the section where she has lunch. Then, $X_3 \leq s \leq X_4$ and $Y_3 \leq t \leq Y_4$ hold.
Let $(u,v)$ be the section where she ends the tour. Then, $X_5 \leq u \leq X_6$ and $Y_5 \leq v \leq Y_6$ hold.
By repeatedly moving to the adjacent section (sharing a side), she travels from the starting section to the ending section in the shortest distance, passing the lunch section on the way.

Two touring plans are considered different if at least one of the following is different: the starting section, the lunch section, the ending section, and the sections that are visited on the way. Joisino would like to know how many different good touring plans there are. Find the number of the different good touring plans. Since it may be extremely large, find the count modulo $10^9+7$ .

Constraints

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

Input

Input is given from Standard Input in the following format:

 $X_1$   $X_2$   $X_3$   $X_4$   $X_5$   $X_6$ 
 $Y_1$   $Y_2$   $Y_3$   $Y_4$   $Y_5$   $Y_6$

Output

Print the number of the different good touring plans, modulo $10^9+7$ .

Sample Input 1Copy

Copy

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

Sample Output 1Copy

Copy

The starting section will always be $(1,1)$ , and the lunch section will always be $(2,2)$ . There are four good touring plans where $(3,3)$ is the ending section, and six good touring plans where $(4,3)$ is the ending section. Therefore, the answer is $6+4=10$ .

Sample Input 2Copy

Copy

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

Sample Output 2Copy

Copy

Sample Input 3Copy

Copy

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

Sample Output 3Copy

Copy

137477680