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$$$.

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.

Subsequence Problem

Examples