I. Организовываем музыкальный фестиваль
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы являетесь организатором известного «Цюрихского музыкального фестиваля». На фестивале будут выступать $$$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$$$) — количество певцов и количество друзей соответственно.

В $$$i$$$-й из следующих $$$m$$$ строк содержится целое число $$$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$$$.

Примеры
Входные данные
3 1
2 1 3
Выходные данные
4
Входные данные
5 5
2 1 2
2 2 3
2 3 4
2 4 5
2 1 5
Выходные данные
0
Входные данные
100 1
1 50
Выходные данные
35305197
Входные данные
5 1
5 1 2 3 4 5
Выходные данные
120
Входные данные
2 5
1 2
1 2
1 2
1 1
1 1
Выходные данные
2
Входные данные
11 4
5 4 5 7 9 11
2 2 10
2 9 11
7 1 2 3 5 8 10 11
Выходные данные
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$$$ возможных порядков правильны.