[AdditionalFile5614.zip](file://AdditionalFile5614.zip?type=additional_file)

#5614. 「PA 2016 Final」Osiągalność

标签: 传统 | 时间限制: 8500 ms | 内存限制: 256 MiB |

题目描述

题目译自 PA 2016 Final Osiągalność

Bajtocja 是一个坐落在海洋中的岛屿，拥有极其丰富的珍贵资源。该岛屿的区域呈正方形，四条边分别指向东西南北四个方向。在 Bajtocja 的西海岸和南海岸已经建成了若干港口。到目前为止，岛上还没有连接这些港口的道路基础设施。然而，由于不利的洋流影响，从西海岸港口航行到南海岸港口（以及随之而来的资源运输）既费时又昂贵。因此，Bajtocja 决定建设一套道路和交叉口网络，以（部分地）解决从西海岸到南海岸的运输问题。遗憾的是，目前已知资金并不足以建造任何地下隧道、高架桥或立交桥。

为了简化计算，我们假设 Bajtocja 的区域是一个正方形，其对角顶点分别位于笛卡尔坐标系的 $(0,0)$ 和 $(10^{9}, 10^{9})$ 点。西海岸的 $n$ 个港口分别位于 $OY$ 轴上的某些点，而南海岸的 $m$ 个港口则位于 $OX$ 轴上的某些点。所有港口的位置两两不同。

道路基础设施的建设方案包括建造（有限数量的）交叉口以及若干条连接交叉口和/或港口的单向道路。道路和交叉口共同构成了道路网络。我们假设交叉口和港口必须位于岛上两两不同的点上，而道路则对应于岛屿区域内任何不自交的曲线，其起点和终点位于交叉口或港口所在的点。两条道路唯一的公共点只能是它们的起点或终点。

下图展示了当 $n=m=2$ 时的三种道路网络示例。灰色区域表示 Bajtocja，黑色方块代表港口，黑色圆圈代表交叉口。

显然，存在无穷多种可能的道路网络。如果对于西海岸的每个港口 $x$ 和南海岸的每个港口 $y$，网络 $A$ 中能从 $x$ 出发通过道路到达 $y$ 当且仅当网络 $B$ 中也能从 $x$ 到达 $y$，则称网络 $A$ 和 $B$ 是等价的。在上述示例中，中间和右侧图中的网络是等价的。

给定 Bajtocja 西海岸和南海岸各港口的位置。请寻找满足上述条件且两两不等价的道路网络构成的最大集合的大小。

输入格式

第一行包含两个整数 $n$ 和 $m$ $(1 \leq n, m \leq 500)$，分别表示岛屿西海岸的港口数量和南海岸的港口数量。

第二行包含 $n$ 个两两不同的整数 $y_{1}, \ldots, y_{n}$ $(1 \leq y_{i} \leq 10^{9})$，描述西海岸港口的位置：其中第 $i$ 个港口位于点 $(0, y_{i})$。

第三行包含 $m$ 个两两不同的整数 $x_{1}, \ldots, x_{m}$ $(1 \leq x_{j} \leq 10^{9})$，描述南海岸港口的位置：其中第 $j$ 个港口位于点 $(x_{j}, 0)$。

输出格式

输出两两不等价的道路网络构成的最大集合的大小，结果对 $10^{9}+7$ 取模。

样例 1

输入

2 2
1 2
1 2

输出

13

样例 2

输入

8 9
39 58 64 23 72 66 80 30
93 23 33 72 79 48 19 92 98

输出

914854829