問題文

$N$ 匹のうさぎがいます。 うさぎは $1$ から $N$ まで番号が振られています。

これら $N$ 匹のうさぎが徒競走をしました。 同着はいませんでした。 このとき、着順は $N!$ 通り考えられます。

高橋君は $M$ 人の観客から情報を集めました。 $i$ 番目の観客によると、うさぎ $x_i$ はうさぎ $y_i$ よりも先にゴールしたそうです。

すべての観客の情報に合致するような着順が何通り考えられるか求めてください。

制約

• $2≦N≦16$
• $1≦M≦N(N-1)/2$
• $1≦x_i，y_i≦N$
• $x_i≠y_i$
• $(x_i，y_i)$ の組はすべて相異なる。
• すべての観客の情報に合致するような着順が少なくともひとつ存在する。

部分点

• $30$ 点分のテストケースでは、$N≦8$ を満たす。

入力

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $x_1$ $y_1$ $x_2$ $y_2$ $:$ $x_M$ $y_M$

出力

すべての観客の情報に合致するような着順が何通り考えられるか出力せよ。

入力例1

3 2
2 1
2 3

出力例1

2

次の $2$ 通りが考えられます。

• $(2，1，3)$
• $(2，3，1)$

入力例2

5 5
1 2
2 3
3 5
1 4
4 5

出力例2

3

次の $3$ 通りが考えられます。

• $(1，2，3，4，5)$
• $(1，2，4，3，5)$
• $(1，4，2，3，5)$

入力例3

16 1
1 2

出力例3

10461394944000

答えは $32$ bit 整数型に収まらない場合があります。 なお、このケースは部分点のテストケースには含まれません。