问题描述

有 $N$ 个编号为 $1,2, \\dots,N$ 的重量。
使用天平，我们将进行 $M$ 次比较。

• 在比较之前，准备一个空字符串 $S$。
• 对于第 $i$ 次比较，将重量 $A_i$ 放在左碗中，将重量 $B_i$ 放在右碗中。
• 然后，会得到以下三种结果之一。
  • 如果重量 $A_i$ 比重量 $B_i$ 更重，
    • 将 > 追加到 $S$ 的末尾。
  • 如果重量 $A_i$ 和重量 $B_i$ 相同质量，
    • 将 = 追加到 $S$ 的末尾。
  • 如果重量 $A_i$ 比重量 $B_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$ 始终是上述 $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