AT_tenka1_2013_final_e 天下一折れ線遊戯

在一个坐标系中，我们规定 $x$ 轴的正方向朝右，$y$ 轴的正方向朝上。 纸上有如下的一些点： - 在左侧，有 $N$ 个红点，坐标分别为 $(0, 0), (0, 1000), \ldots, (0, 1000(N-1))$。 - 在右侧，有 $N$ 个蓝点，坐标分别为 $(10^9, 0), (10^9, 1000), \ldots, (10^9, 1000(N-1))$。 - $M$ 个黑点，坐标为 $(X_k, Y_k)$。 需要注意的是，这些黑点的 $x$ 坐标互不相同。高桥君热爱折线。 对于每个点 $(x_k, y_k)$，有以下四种操作可以选择： 1. 不做任何处理。 2. 在 ($x > x_k, y > y_k$) 的区域内，选取 $y$ 坐标最小的点与之相连。如果这样的点有多个，那么选择最近的那个。如果没有点符合要求，则不进行连接。 3. 在 ($x > x_k, y < y_k$) 的区域内，选择 $y$ 坐标最大的点与之相连。如果这样的点有多个，选择最近的那个。如果没有点符合要求，则不进行连接。 4. 在 $x > x_k, y = y_k$ 的区域内，选择最近的点与之相连。如果没有符合要求的点，则不进行连接。 高桥君的目标是确保每个红点都能通过一系列连续的线段最终连接到一个蓝点，并且所有的折线互不相交、互不接触。此外，不能有多余的线段存在。 请计算出有多少种方式能够绘制出恰好 $N$ 条这样的折线，使得其互不相交，并输出该数量对 $10^9+7$ 取模的结果。 两种方案是不同的，当且仅当某两个点在一种方案中有连线而在另一种方案中没有。 ### 输入格式 - 第一行输入两个整数 $N$ 和 $M$，分别代表红点和蓝点的数量，以及黑点的数量。 - 接下来 $M$ 行，每行输入两个整数 $X_i$ 和 $Y_i$，代表每个黑点的坐标。 ### 输出格式 输出一个整数，表示满足条件的折线组合数量，对 $10^9+7$ 取模。 ### 数据范围与提示 - $1 \leq N \leq 3$ - $0 \leq M \leq 100000$ - 红点和蓝点的数量相等 - 黑点的 $x$ 坐标两两不同，点的坐标两两不同。 - 部分分：如果 $N=1$ 时正确则可以得到 $60$ 分；如果 $0 \leq M \leq 40$ 时正确，那么可以获得额外 $60$ 分。 ### 示例 #### 输入示例 1 ``` 2 2 100 100 110 110 ``` #### 输出示例 1 ``` 5 ``` #### 输入示例 2 ``` 1 3 500 800 300 500 400 400 ``` #### 输出示例 2 ``` 3 ``` #### 输入示例 3 ``` 2 2 1000 0 2000 1000 ``` #### 输出示例 3 ``` 1 ``` #### 输入示例 4 ``` 3 8 500 5000 3500 5000 2000 3500 1500 2000 2500 2000 1000 1000 3000 1000 1 1 ``` #### 输出示例 4 ``` 48 ``` #### 输入示例 5 ``` 3 0 ``` #### 输出示例 5 ``` 1 ``` 对于示例 5，红点可以直接与右侧的蓝点相连，且线条不相交。结果只有一种方式。

无

无