AiScReam

• サンプル1の説明が適切でなかったため修正しました。(2025/12/17 3:23)

問題文

moguさんは、$1$ から $N$ までの整数について、$M$ 個の質問を投げられ、それぞれ次のように答えました。

• moguさんは、$1$ から $N$ までの整数 $a_i,b_i$ について、 $a_i$ よりも $b_i$ の方が好きである。

$1$ から $N$ までの整数を並び替えてできる数列 $P = (p_1,p_2,...,p_N)$ のうち、全ての　$i(1 \leq i \leq M)$ について $p_{b_i} < p_{a_i}$ を満たすようなものの個数を $998244353$ で割った余りを求めてください。

制約

• $2 \leq N \leq 20$
• $1 \leq M \leq N(N-1)$
• $1 \leq a_i,b_i \leq N$
• $a_i \neq b_i$
• 条件を満たす $P$ は必ず存在する。

入力

入力はすべて整数である。

N M
a_1 b_1
a_2 b_2
...
a_M b_M

出力

$1$ から $N$ までの整数を並び替えてできる数列 $P = (p_1,p_2,...,p_N)$ のうち、全ての　$i(1 \leq i \leq M)$ について $p_{b_i} < p_{a_i}$ を満たすようなものの個数を $998244353$ で割った余りを1行に出力せよ。

サンプル

4 2
1 2
2 3

4

条件より、$p_3 < p_2 < p_1$ となります。残った $p_4$ は $p_1,p_2,p_3$ で使われなかった $1$ 個の整数なので、条件を満たす数列の個数は $p_4$ の選び方の総数より $4$ 個となります。

2 1
2 1

1

条件を満たす数列は $P = (1,2)$ しかありえません。

5 3
3 4
1 3
2 3

10