問題文

この世界では文字は$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つのゲームが異なるとは、単語を選ぶ順番が異なることをいう。

入力

$NM$
$A_1{B}_1$
$⋮$
$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\ne j$なら$(A_i,B_i)\ne (A_j,B_j)$である。

出力

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

サンプル

2 1
1 2

1

2 0

4

2 4
2 2
1 2
1 1
2 1

1

3 3
1 3
3 1
3 2

2

3 0

216

10 0

276247125