分数: 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.
示例输入 1
1 1 2 2 3 4 1 1 2 2 3 3
示例输出 1
10
起始部分始终是 (1,1),午餐部分将始终是 (2,2)。 有四个不错的旅游计划 (3,3) 是结局部分,还有六个好的巡演计划 (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