F. Задача о подпоследовательностях
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Даны три целых числа $$$n, m, k$$$, а также $$$k$$$ массивов целых чисел длин $$$l_1, l_2, \dots, l_k$$$ соответственно. Обозначим элемент под номером $$$j$$$ в массиве под номером $$$i$$$ за $$$a_{i,j}$$$. В каждом массиве все элементы различны (но могут повторяться в разных массивах).

Назовем массив $$$b$$$ длины $$$k$$$ красивым, если для каждого $$$i$$$ от $$$1$$$ до $$$k$$$ элемент $$$b_i$$$ равен одному из элементов массива $$$a_i$$$.

Назовем массив $$$c$$$ идеальным, если каждый красивый массив $$$b$$$ можно получить из массива $$$c$$$ удалением нескольких (возможно, нуля) элементов без изменения их порядка. Иными словами, массив $$$c$$$ идеальный, если каждый красивый массив $$$b$$$ является его подпоследовательностью.

Ваша задача — посчитать количество идеальных массивов $$$c$$$ длины $$$n$$$, все элементы которых от $$$1$$$ до $$$m$$$.

Входные данные

В первой строке заданы три целых числа $$$n, m, k$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$5 \le m \le 10^8$$$; $$$2 \le k \le n$$$).

Во второй строке заданы $$$k$$$ целых чисел $$$l_1, l_2, \dots, l_k$$$ ($$$1 \le l_i \le 5$$$).

Далее следуют $$$k$$$ строк, в $$$i$$$-й из них заданы $$$l_i$$$ различных целых чисел $$$a_{i,1}, a_{i,2}, \dots, a_{i,l_i}$$$ ($$$1 \le a_{i,j} \le m$$$).

Дополнительное ограничение на входные данные: сумма $$$l_i$$$ не превосходит $$$n$$$.

Выходные данные

Выведите одно целое число — количество идеальных массивов длины $$$n$$$, все элементы которых от $$$1$$$ до $$$m$$$. Так как ответ может быть очень большим, выведите его по модулю $$$998244353$$$.

Примеры
Входные данные
4 5 3
1 1 2
4
1
4 3
Выходные данные
2
Входные данные
3 5 2
1 1
5
2
Выходные данные
13
Входные данные
200000 12345678 7
3 2 5 1 3 4 5
42 13 37
37 13
1 2 3 4 5
3
3 1 4
1 5 9 2
1 2 3 4 5
Выходные данные
152094503
Примечание

В первом примере есть два красивых массива: $$$[4, 1, 4]$$$ и $$$[4, 1, 3]$$$. Только два массива длины $$$4$$$ содержат оба эти массива как подпоследовательности: $$$[4, 1, 4, 3]$$$ и $$$[4, 1, 3, 4]$$$.

Во втором примере только один красивый массив: $$$[5, 2]$$$. Существует $$$13$$$ массивов длины $$$3$$$ с числами от $$$1$$$ до $$$5$$$, содержащих его как подпоследовательность.