题目描述

Joisino 计划游览高桥镇。该镇以南北和东西两个方向的线将其分成方块区域。我们将从西边数第 $x$ 个，从北边数第 $y$ 个的区域称为 $(x,y)$。

Joisino 认为一个 游览计划 如果满足以下条件就是好的：

• 假设她开始游览的区域是 $(p,q)$。那么，必须满足 $X_1 ≤ p ≤ X_2$ 和 $Y_1 ≤ q ≤ Y_2$。

• 假设她午餐的地方是 $(s,t)$。那么，必须满足 $X_3 ≤ s ≤ X_4$ 和 $Y_3 ≤ t ≤ Y_4$。

• 假设她游览结束的区域是 $(u,v)$。那么，必须满足 $X_5 ≤ u ≤ X_6$ 和 $Y_5 ≤ v ≤ Y_6$。

• 通过重复移动到相邻区域（共享一条边），她以最短的距离从起始区域到达结束区域，途中经过午餐区域。

如果起始区域、午餐区域、结束区域以及前往途中访问的区域之一不同，那么两个游览计划被认为是不同的。Joisino 想知道有多少种不同的好游览计划。找出不同的好游览计划的数量。由于数量可能非常大，计算结果取模 $10^9+7$。

约束条件

• $1 ≤ X_1 ≤ X_2 < X_3 ≤ X_4 < X_5 ≤ X_6 ≤ 10^6$
• $1 ≤ Y_1 ≤ Y_2 < Y_3 ≤ Y_4 < Y_5 ≤ Y_6 ≤ 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$。

示例输入1

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

示例输出1

10

起始区域始终为 $(1,1)$，午餐区域始终为 $(2,2)$。存在 $4$ 种好的游览计划，其中结束区域为 $(3,3)$，存在 $6$ 种好的游览计划，其中结束区域为 $(4,3)$。因此答案是 $6+4=10$。

示例输入2

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

示例输出2

2346

示例输入3

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

示例输出3

137477680