No.310 2文字しりとり

レベル : / 実行時間制限 : 1ケース 6.000秒 / メモリ制限 : 512 MB / タグ : / 解いたユーザー数 6
作問者 : anta

4 ProblemId : 874

問題文

この世界では文字は$N$種類あり、$1$から$N$までの整数で表される。 2文字の単語は、1文字目を$a$, 2文字目を$b$としたとき、2つの文字の組$(a,b)$として表される。 この世界は単語が豊富であり、$M$個の存在しない単語を除く全ての単語は辞書に載っている。つまり、$N^2 - M$個の単語が辞書に載っている。

特殊なルールのしりとり「2文字しりとり」をすることにした。このしりとりは1人で行う。 2文字しりとりの1回のゲームは以下のようにして行われる。

  1. まず初めに辞書から単語を1つ選ぶ。
  2. このゲームでまだ選んでいない辞書中の単語のうち、最後に選んだ単語の2文字目と新たに選ぶ単語の1文字目が一致するようなものを1つ選ぶ。 つまり、最後に単語$(a,b)$を選んだあと新たに単語$(c,d)$を選ぶ場合、$b = c$でなければならない。 そのように単語を選ぶことを繰り返す。
  3. 選べる単語が無くなった時点でゲームは終了となる。

1回のゲームで辞書中の$N^2 - M$個全ての単語を選んだ場合、そのゲームを完全であるという。

完全なゲームは何通りあるか?$1000000007$で割った余りを求めよ。 ただし、2つのゲームが異なるとは、単語を選ぶ順番が異なることをいう。

入力

$N\ M$
$A_1\ B_1$
$\quad\vdots$
$A_M\ B_M$

1行目に、文字の種類数を表す整数$N$, 存在しない単語の個数を表す整数$M$が空白区切りで与えられる。
2行目以降$M$行に、存在しない単語のリストが与えられる。 それぞれの$i$ ($1 \le i \le M$)に対し、$1 \le A_i, B_i \le N$であり、$(A_i,B_i)$の単語が存在しないことを表す。

  • $1 \le N \le 4000$
  • $0 \le M \le 4000$
  • 存在しない単語は重複しない。つまり、$i \neq j$なら$(A_i,B_i) \neq (A_j,B_j)$である。

出力

完全なゲームが何通りあるかを表す整数を$1000000007$で割った余りを1行に出力せよ。

サンプル

サンプル1
入力
2 1
1 2
出力
1

辞書に載っている単語は$(1,1), (2,2), (2,1)$の3つである。 この3つ全ての単語を選ぶためには必ず$(2,2), (2,1), (1,1)$の順番で選ばなければならない。 よって、答えは1となる。

サンプル2
入力
2 0
出力
4

最初にどの単語を選ぶ場合にもそれぞれ1通りあり、合計4通りとなる。

サンプル3
入力
2 4
2 2
1 2
1 1
2 1
出力
1

空のゲームも数える。

サンプル4
入力
3 3
1 3
3 1
3 2
出力
2
サンプル5
入力
3 0
出力
216
サンプル6
入力
10 0
出力
276247125

$1000000007$で割った余りを出力することに注意せよ。

提出ページヘ