問題文

$1,2, \\dots,N$ の番号の付いた $N$ 個のおもりがあります。
これから天秤を用いて $M$ 回の重さの比較を行います。

• 比較開始前に、空文字列 $S$ を用意する。
• $i$ 回目の比較では、左の皿におもり $A_i$ のみを、右の皿におもり $B_i$ のみを乗せる。
• この際、以下の $3$ 通りのうちいずれかの結果が得られる。
  • おもり $A_i$ の方がおもり $B_i$ より重い。
    • この際 $S$ の末尾に > を加える。
  • おもり $A_i$ とおもり $B_i$ は同じ重さである。
    • この際 $S$ の末尾に = を加える。
  • おもり $B_i$ の方がおもり $A_i$ より重い。
    • この際 $S$ の末尾に < を加える。
• 天秤が誤った結果を出すことはない。

実験終了後、長さ $M$ の文字列 $S$ が得られます。
>, =, < からなる長さ $M$ の文字列は $3^M$ 通りありますが、そのうち実験で得られた $S$ として考えられるものは何通りありますか?
答えは非常に大きくなることがあるので、 $998244353$ で割った余りを出力してください。

制約

• 入力は全て整数
• $2 \\le N \\le 17$
• $1 \\le M \\le \\frac{N \\times (N-1)}{2}$
• $1 \\le A_i < B_i \\le N$
• $i \\neq j \\Rightarrow (A_i,B_i) \\neq (A_j,B_j)$

入力

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

$N$ $M$ $A_1$ $B_1$ $A_2$ $B_2$ $\\vdots$ $A_M$ $B_M$

出力

答えを整数として出力せよ。

入力例 1

3 3
1 2
1 3
2 3

出力例 1

13

おもりの重さをおもりの番号順に書き並べた数列を $w$ とします。

• $w=(5,5,5)$ の時 $S=$ ===
• $w=(2,2,3)$ の時 $S=$ =<<
• $w=(6,8,6)$ の時 $S=$ <=>
• $w=(9,4,4)$ の時 $S=$ >>=
• $w=(7,7,3)$ の時 $S=$ =>>
• $w=(8,1,8)$ の時 $S=$ >=<
• $w=(5,8,8)$ の時 $S=$ <<=
• $w=(1,2,3)$ の時 $S=$ <<<
• $w=(4,9,5)$ の時 $S=$ <<>
• $w=(5,1,8)$ の時 $S=$ ><<
• $w=(6,9,2)$ の時 $S=$ <>>
• $w=(7,1,3)$ の時 $S=$ >><
• $w=(9,7,5)$ の時 $S=$ >>>

という文字列 $S$ を得ます。
他にもおもりの重さとして考えられる列は無数にありますが、 $S$ として考えられるのは以上の $13$ 通りです。

入力例 2

4 4
1 4
2 3
1 3
3 4

出力例 2

39

入力例 3

14 15
1 2
1 3
2 4
2 5
2 6
4 8
5 6
6 8
7 8
9 10
9 12
9 13
10 11
11 12
11 13

出力例 3

1613763