← 返回题目列表

AtCoder · tenka1_2013_final_e

E. 天下一线游戏

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

問題文

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 所有坐标都不同。

高桥君喜欢折线。

每点 (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 做一件事。

高桥君刚刚为所有红点画了一条折线。 1 我希望它连接到两个蓝点。

每条折线不得相交或接触。另外, 请勿绘制 N 折线中未包含的不必要的线段。

N Mod 有多少种绘制折线的方法。 使用 1000000007 找到它。


入力

输入按以下格式给出。

N M
X_1 Y_1
X_2 Y_2
:
X_M Y_M
  1. 1 行显示红色和蓝色点的数量。 N\ (1 ≦ N ≦ 3) 和黑点的数量 M\ (0 ≦ M ≦ 100000) 是 1 行输入 直到
  2. 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)
和 按字典顺序比较 5 有几种方法。


入力例 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 有几种方法。


入力例 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

将每个红点直接连接到右侧的蓝点。

没有其他方法可以绘制线条,因为它们不能相交。