AT_abc306_h.[ABC306Ex] Balance Scale

有 $N$ 个编号为 $1,2,\dots,N$ 的砝码。
接下来你将用天平进行 $M$ 次重量比较。

• 在比较开始前，准备一个空字符串 $S$。
• 第 $i$ 次比较时，将砝码 $A_i$ 放在天平左盘，将砝码 $B_i$ 放在右盘。
• 此时会得到以下三种结果之一：
  • 砝码 $A_i$ 比砝码 $B_i$ 重。
    • 此时在 $S$ 的末尾添加 >。
  • 砝码 $A_i$ 和砝码 $B_i$ 重量相同。
    • 此时在 $S$ 的末尾添加 =。
  • 砝码 $B_i$ 比砝码 $A_i$ 重。
    • 此时在 $S$ 的末尾添加 <。
• 天平不会给出错误的结果。

实验结束后，你会得到一个长度为 $M$ 的字符串 $S$。
由 >、=、< 组成的长度为 $M$ 的字符串共有 $3^M$ 种，但作为实验结果可能出现的 $S$ 有多少种？
由于答案可能非常大，请输出其对 $998244353$ 取模的结果。

输入以如下格式从标准输入读入。

$N\ M$

$A_1\ B_1$

$A_2\ B_2$

$\vdots$

$A_M\ B_M$

请输出答案的整数值。

限制条件

• 所有输入均为整数。
• $2 \leq N \leq 17$
• $1 \leq M \leq \frac{N \times (N-1)}{2}$
• $1 \leq A_i < B_i \leq N$
• $i \neq j \Rightarrow (A_i,B_i) \neq (A_j,B_j)$

样例解释 1

将砝码的重量按编号顺序排列成数列 $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$ 种。

由 ChatGPT 4.1 翻译，123asdf123 修缮。