配点 : 500 点
問題文
高桥是偶像团体Bit♡Beat的粉丝,也是成员。 N 适合所有人的亚克力支架 1 我各有一个。
高桥君 我正在尝试将 N 亚克力支架排成一排,但我正在尝试 2 我们认为人们不应该相邻放置。具体来说, 对于 i=1,2,\ldots,M 反对 A_i 与第 名成员 B_i 我想安排第三位成员的亚克力支架,使它们不彼此相邻。
高桥的 M 满足所有个人需求 N 亚克力支架有多少种排列方式? 除以 998244353 后求余数。
制約
- 2\le N\le 10^6
- 0\le M\le 16
- 1\le A_i < B_i \le N
- (A_i , B_i) \neq (A_j , B_j) (i \neq j)
- 所有输入值均为整数
入力
输入将以以下格式从标准输入给出。
N M A_1 B_1 A_2 B_2 \vdots A_M B_M
出力
打印答案。
入力例 1
3 1 1 2
出力例 1
2
下面 2 两个排列满足条件。
- 2 第会员, 3 第会员, 1 与成员的亚克力支架按顺序排列。
- 1 第会员, 3 第会员, 2 与成员的亚克力支架按顺序排列。
因此, 请输出 2 。
入力例 2
5 4 1 4 1 2 1 5 1 3
出力例 2
0
没有满足条件的排序方法。因此, 请打印除以 0 。
入力例 3
15 5 3 8 8 9 8 12 4 9 4 7
出力例 3
720555423
998244353 后的余数。