問題文

アイドルグループ Bit♡Beat のファンである高橋君はメンバー N 人全員のアクリルスタンドを 1 つずつ持っています。

高橋君は N 個のアクリルスタンドを一列に並べようとしていますが、特定の 2 人を隣に並べてはいけないと考えています。具体的には、 i=1,2,\ldots,M に対し A_i 人目のメンバーと B_i 人目のメンバーのアクリルスタンドが隣り合わないように並べたいと考えています。

高橋君の M 個の要望を全て満たすような N 個のアクリルスタンドの並べ方が何通りあるかを 998244353 で割ったあまりを求めてください。

制約

• 2\le N\le 10^6
• 0\le M\le 16
• 1\le A_i < B_i \le N
• (A_i , B_i) \neq (A_j , B_j) (i \neq j)
• 入力される値は全て整数である

入力例 1

3 1
1 2

出力例 1

2

以下の 2 つの並べ方が条件を満たします。

• 2 人目のメンバー、 3 人目のメンバー、 1 人目のメンバーのアクリルスタンドと順に並べる。
• 1 人目のメンバー、 3 人目のメンバー、 2 人目のメンバーのアクリルスタンドと順に並べる。

したがって、 2 を出力してください。

入力例 2

5 4
1 4
1 2
1 5
1 3

出力例 2

0

条件を満たす並べ方は存在しません。したがって、 0 を出力してください。

入力例 3

15 5
3 8
8 9
8 12
4 9
4 7

出力例 3

720555423

998244353 で割ったあまりを出力してください。