AT_agc018_e.[AGC018E] Sightseeing Plan

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 \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 翻译