天平

题目描述

有 $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$ 取模后输出。

输入格式

输入按以下格式从标准输入给出。

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

输出格式

将答案作为整数输出。

样例

3 3
1 2
1 3
2 3

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$ 种之一。

4 4
1 4
2 3
1 3
3 4

39

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

1613763

数据范围

• 所有输入值都是整数。
• $2 \le N \le 17$
• $1 \le M \le \frac{N \times (N-1)}{2}$
• $1 \le A_i \lt B_i \le N$
• $i \neq j \Rightarrow (A_i,B_i) \neq (A_j,B_j)$