天下一プログラマーコンテスト2013 決勝

E - 天下一折れ線遊戯


Time limit時間制限 : 4sec / Memory limitメモリ制限 : 64MB

問題文

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つ目の赤い点(赤1)、(0,\ 1000) が2つ目の赤い点(赤2)、 (1000000000,\ 0) が1つ目の青い点(青1)、(1000000000,\ 1000) が2つ目の青い点(青2)、 (100,\ 100) が1つ目の黒い点(黒1)、(110,\ 110) が2つ目の黒い点(黒2)、と合計で 6 個の点があります。

  • 赤1から線分を引けるのは黒1または青1のみ、
  • 赤2から線分を引けるのは黒2または青2のみ、
  • 黒1から線分を引けるのは黒2または青1のみ、
  • 黒2から線分を引けるのは青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つ目の赤い点(赤1)、 (1000000000,\ 0) が1つ目の青い点(青1)、 (500,\ 800) が1つ目の黒い点(黒1)、(300,\ 500) が2つ目の黒い点(黒2)、(400,\ 400) が3つ目の黒い点(黒3)と合計で 5 個の点があります。

  • 赤1から線分を引けるのは黒3または青1のみ、
  • 黒1から線分を引けるのは青1のみ、
  • 黒2から線分を引けるのは黒1または黒3のみ、
  • 黒3から線分を引けるのは黒1または黒2のみ

となります。

赤1と青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

それぞれの赤い点は、まっすぐ右にある青い点と結びます。

それぞれの折れ線は交差できないため、これ以外の引き方はありません。


Submit提出する