← 返回题目列表

Codeforces · 1552/I

I. 组织音乐节

中文机器翻译题面 查看原题

你是著名的“苏黎世音乐节”的组织者。将有 $$$n$$$ 歌手在音乐节上表演,由整数 $$$1$$$、$$$2$$$、$$$\dots$$$、$$$n$$$ 标识。您必须选择他们在舞台上表演的顺序。

你有 $$$m$$$ 个朋友,他们每个人都有一组最喜欢的歌手。更准确地说,对于每个 $$$1\le i\le m$$$,第 $$$i$$$ 个朋友喜欢歌手 $$$s_{i,1}, \, s_{i, 2}, \, \dots, \,s_{i, q_i}$$$。

如果你的朋友喜欢的歌手连续表演(以任意顺序),他会很高兴。如果你所有的朋友都高兴的话,歌手的排序就是有效的。

计算有效排序数以 $$$998\,244\,353$$$ 为模。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1\le n,\,m\le 100$$$) — 对应歌手数量和好友数量。

接下来的 $$$m$$$ 行中的第 $$$i$$$ 行包含整数 $$$q_i$$$ ($$$1\le q_i\le n$$$) — 第 $$$i$$$ 位朋友最喜欢的歌手数量 – 后跟 $$$q_i$$$ 整数 $$$s_{i,1}, \, s_{i, 2}, \, \dots, \,s_{i, q_i}$$$ ($$$1\le s_{i,1}<s_{i,2}<\cdots<s_{i,q_i}\le n$$$) — 他最喜欢的歌手的索引。

输出

打印歌手的有效排序数,以 $$$998\,244\,353$$$ 为模。

示例

输入 #1

3 1
2 1 3

输出 #1

4

输入 #2

5 5
2 1 2
2 2 3
2 3 4
2 4 5
2 1 5

输出 #2

0

输入 #3

100 1
1 50

输出 #3

35305197

输入#4

5 1
5 1 2 3 4 5

输出#4

120

输入 #5

2 5
1 2
1 2
1 2
1 1
1 1

输出 #5

2

输入 #6

11 4
5 4 5 7 9 11
2 2 10
2 9 11
7 1 2 3 5 8 10 11

输出 #6

384

注意

第一个样本的解释:有 $$$3$$$ 歌手,只有 $$$1$$$ 朋友。这位朋友喜欢两位歌手$$$1$$$ 和$$$3$$$。因此,$$$4$$$ 的有效顺序是:

- 1 3 2
- 2 1 3
- 2 3 1
- 3 1 2

第二个样本的解释:有$$$5$$$歌手和$$$5$$$朋友。可以证明没有订单是有效的。

第三个样本的解释:有$$$100$$$歌手,只有$$$1$$$朋友。该朋友只喜欢歌手 $$$50$$$,因此所有 $$$100!$$$ 可能的订单都是有效的。

第四个样本的解释:有$$$5$$$歌手,只有$$$1$$$朋友。该朋友喜欢所有歌手,因此所有 $$$5!=120$$$ 可能的订单都是有效的。