問題文
x 坐标正方向向右,y 坐标正方向向上。
在纸面上,
- 向左 N 红点 (0,\ 0),\ (0,\ 1000),\ ...,\ (0,\ 1000(N-1))
- 向右 N 蓝点 (10^9,\ 0),\ (10^9,\ 1000),\ ..., (10^9,\ 1000(N-1))
- M 黑点 有 (X_k,\ Y_k)
高桥君喜欢折线。
每点 (x_k,\ y_k) , 当我输入
- 不执行任何操作
- x > x_k,\ y > y_k中的点中, y 用线段连接坐标值最小的点。如果有多个这样的点,请使用线段将它们与最近的点连接起来。如果没有这样的点,则不执行任何操作。
- x > x_k,\ y < y_k中的点中, y 用线段连接坐标值最大的点。如果有多个这样的点,请使用线段将它们与最近的点连接起来。如果没有这样的点,则不执行任何操作。 在区域
- x > x_k,\ y = y_k中的点中,用线段将它们与最近的点连接起来。如果没有这样的点,则不执行任何操作。
高桥君刚刚为所有红点画了一条折线。 1 我希望它连接到两个蓝点。
每条折线不得相交或接触。另外, 请勿绘制 N 折线中未包含的不必要的线段。
N Mod 有多少种绘制折线的方法。 使用 1000000007 找到它。
入力
输入按以下格式给出。
N M X_1 Y_1 X_2 Y_2 : X_M Y_M
- 1 行显示红色和蓝色点的数量。 N\ (1 ≦ N ≦ 3) 和黑点的数量 M\ (0 ≦ M ≦ 100000) 是 1 行输入 直到
- 2 从行 M+1 行
在 M 行中,
一个整数,表示i 第一个黑点 x 坐标和 y 代表坐标的整数 X_i,\ Y_i\ (0 < X_i < 10^9,\ 0 ≦ Y_i ≦ 10^9) 。
表示
- 黑点 x 坐标彼此不同。换句话说,i \neq j 时,X_i \neq X_j 满足
部分点
- N = 1如果输入正确,320 部分积分换满分 60 点。 如果您正确回答了所有满足
- 0 ≦ M ≦ 40 如果输入正确,320 与以上分开作为部分分数换为满分。 60 点。 如果您正确回答了所有满足
出力
高桥可以拉, 输出绘制 N 折线的方法数量。如果组合 1000000007 如果超过这个数量, 打印除以 1000000007 请输出除以 的余数。
另外,在输出末尾放置一个换行符。
入力例 1
2 2 100 100 110 110
出力例 1
5
(0,\ 0) 是第一个红点(红色1),(0,\ 1000) 是第二个红点(红色2), (1000000000,\ 0) 是第一个蓝点(蓝色 1),(1000000000,\ 1000) 是第二个蓝点(蓝色 2), (100,\ 100) 是第一个黑点(黑色1),(110,\ 110) 是第二个黑点(黑色 2),总共 有 6 有一点。
- 只有黑色 1 或蓝色 1 可以从红色 1 绘制线段。
- 只有黑色 2 或蓝色 2 可以从红色 2 绘制线段。
- 只有黑色 2 或蓝色 1 可以从黑色 1 绘制线段。
- 只有蓝色 1 或蓝色 2 可以从黑色 2 绘制线段。
。 对于
创建两条不相交或接触的多边形线
- (赤1 - 黒1 - 黒2 - 青1、赤2 - 青2)
- (赤1 - 黒1 - 青1、赤2 - 黒2 - 青2)
- (赤1 - 黒1 - 青1、赤2 - 青2)
- (赤1 - 青1、赤2 - 黒2 - 青2)
- (赤1 - 青1、赤2 - 青2)
入力例 2
1 3 500 800 300 500 400 400
出力例 2
3
(0,\ 0) 是第一个红点(红色1), (1000000000,\ 0) 是第一个蓝点(蓝色 1), (500,\ 800) 是第一个黑点(黑色1),(300,\ 500) 是第二个黑点(黑色2),(400,\ 400) 是第三个黑点(黑色 3),总计 5 有一点。
- 只有黑色 3 或蓝色 1 可以从红色 1 绘制线段。
- 只有蓝色1可以从黑色1绘制线段,
- 只有黑1或黑3可以从黑2画一条线段。
- 只有黑1或黑2可以从黑3画一条线段。
。 对于
创建连接 Red 1 和 Blue 1 的折线
- (赤1 - 青1)
- (赤1 - 黒3 - 青1)
- (赤1 - 黒3 - 黒1 - 青1)
入力例 3
2 2 1000 0 2000 1000
出力例 3
1
红点从下到红1,红2, 蓝点从下往上依次为蓝1、蓝2、 按照输入给定的顺序将黑点设置为黑色 1 和黑色 2。
- (赤1 - 黒1 - 青1、赤2 - 黒2 - 青2)
和 按字典顺序比较 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
将每个红点直接连接到右侧的蓝点。
没有其他方法可以绘制线条,因为它们不能相交。