F. Subsequence Problem
time limit per test
4 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Given three integers $$$n, m, k$$$, as well as $$$k$$$ arrays of integers of lengths $$$l_1, l_2, \dots, l_k$$$ respectively. We denote the element at position $$$j$$$ in array number $$$i$$$ as $$$a_{i,j}$$$. In each array, all elements are distinct (but may repeat in different arrays).

We call an array $$$b$$$ of length $$$k$$$ beautiful if for each $$$i$$$ from $$$1$$$ to $$$k$$$, the element $$$b_i$$$ is equal to one of the elements of the array $$$a_i$$$.

We call an array $$$c$$$ perfect if every beautiful array $$$b$$$ can be obtained from array $$$c$$$ by deleting several (possibly zero) elements without changing their order. In other words, array $$$c$$$ is perfect if every beautiful array $$$b$$$ is a subsequence of it.

Your task is to count the number of perfect arrays $$$c$$$ of length $$$n$$$ containing only integers from $$$1$$$ to $$$m$$$.

Input

The first line contains three integers $$$n, m, k$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$5 \le m \le 10^8$$$; $$$2 \le k \le n$$$).

The second line contains $$$k$$$ integers $$$l_1, l_2, \dots, l_k$$$ ($$$1 \le l_i \le 5$$$).

The following $$$k$$$ lines contain the $$$i$$$-th line with $$$l_i$$$ distinct integers $$$a_{i,1}, a_{i,2}, \dots, a_{i,l_i}$$$ ($$$1 \le a_{i,j} \le m$$$).

Additional constraint on the input: the sum of $$$l_i$$$ does not exceed $$$n$$$.

Output

Print one integer — the number of perfect arrays of length $$$n$$$ such that they contain only integers from $$$1$$$ to $$$m$$$. Since the answer may be very large, output it modulo $$$998244353$$$.

Examples
Input
4 5 3
1 1 2
4
1
4 3
Output
2
Input
3 5 2
1 1
5
2
Output
13
Input
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
Output
152094503
Note

In the first example, there are two beautiful arrays: $$$[4, 1, 4]$$$ and $$$[4, 1, 3]$$$. Only two arrays of length $$$4$$$ contain both of these arrays as subsequences: $$$[4, 1, 4, 3]$$$ and $$$[4, 1, 3, 4]$$$.

In the second example, there is only one beautiful array: $$$[5, 2]$$$. There are $$$13$$$ arrays of length $$$3$$$ with integers from $$$1$$$ to $$$5$$$ that contain it as a subsequence.