← 返回题目列表

AtCoder · agc018_e

E. 观光计划

中文机器翻译题面 查看原题

分数: 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