题目描述

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 1 2 2 3 4
1 1 2 2 3 3

输出

10

样例 2

输入

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

输出

2346

样例 3

输入

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

输出

137477680

说明/提示

限制条件

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

样例解释 1

观光开始区域只能为 $(1, 1)$，吃午饭的区域只能为 $(2, 2)$。
当观光结束区域为 $(3, 3)$ 时，移动方式有 $4$ 种；观光结束区域为 $(4, 3)$ 时，移动方式有 $6$ 种。
所以这个样例的答案为 $6+4=10$ 种。

由 ChatGPT 5 翻译