你是著名的“苏黎世音乐节”的组织者。将有 $$$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$$$ 可能的订单都是有效的。