/ 
Time Limit: 4 sec / Memory Limit: 64 MB
問題文
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つ目の赤い点（赤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）
入力例 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
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
それぞれの赤い点は、まっすぐ右にある青い点と結びます。
それぞれの折れ線は交差できないため、これ以外の引き方はありません。