Вы являетесь организатором известного «Цюрихского музыкального фестиваля». На фестивале будут выступать \(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\).
Выходные данные
Выведите количество правильный порядков выступлений по модулю \(998\,244\,353\).
Примечание
Объяснение первого примера: Есть \(3\) певца и только \(1\) друг. Другу нравятся два певца \(1\) и \(3\). Таким образом, \(4\) правильных порядка:
Объяснение второго примера: Есть \(5\) певцов и \(5\) друзей. Можно показать, что правильных порядков нет.
Пояснение третьего примера: Есть \(100\) певцов и только \(1\) друг. Другу нравится только певец \(50\), следовательно, все \(100!\) возможных порядков правильны.
Пояснение четвертого примера: Есть \(5\) певцов и только \(1\) друг. Другу нравятся все певцы, следовательно, все \(5!=120\) возможных порядков правильны.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 1
2 1 3
|
4
|
|
2
|
5 5
2 1 2
2 2 3
2 3 4
2 4 5
2 1 5
|
0
|
|
3
|
100 1
1 50
|
35305197
|
|
4
|
5 1
5 1 2 3 4 5
|
120
|
|
5
|
2 5
1 2
1 2
1 2
1 1
1 1
|
2
|
|
6
|
11 4
5 4 5 7 9 11
2 2 10
2 9 11
7 1 2 3 5 8 10 11
|
384
|