分数: 650 点
问题陈述
有 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.
- 追加
- 如果重量 A_i 比重量重 B_i,
- 结果始终准确。
实验结束后,你会得到一个字符串 S 长度 M.
其中 3^M 长度的字符串 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 是重量的质量序列,按重量编号的升序排列。
- If w=(5,5,5),您获得 S=
===. - If w=(2,2,3),您获得 S=
=<<. - If w=(6,8,6),您获得 S=
<=>. - If w=(9,4,4),您获得 S=
>>=. - If w=(7,7,3),您获得 S=
=>>. - If w=(8,1,8),您获得 S=
>=<. - If w=(5,8,8),您获得 S=
<<=. - If w=(1,2,3),您获得 S=
<<<. - If w=(4,9,5),您获得 S=
<<>. - If w=(5,1,8),您获得 S=
><<. - If w=(6,9,2),您获得 S=
<>>. - If w=(7,1,3),您获得 S=
>><. - If 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