I. Expected Value
time limit per test
12 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

For a set $$$S$$$ and an array $$$a$$$ of length $$$n$$$, where $$$n$$$ is even, define $$$f(a, S)$$$ to be the number of permutations $$$p$$$ of $$$\{1,2,\ldots,n \}$$$ such that $$$a_{p_i}+a_{p_{n-i+1}} \in S$$$ for all $$$1 \le i \le n$$$.

You are given a set $$$T$$$ and $$$m$$$ sets $$$A_1,A_2,\ldots,A_m$$$, where $$$m$$$ is even. Now construct another array $$$b$$$ as follows:

  1. Initialise $$$b$$$ as an empty array.
  2. For each index from $$$1$$$ to $$$m$$$:
    • Choose an integer from $$$A_i$$$ randomly, with the probability of selecting each integer proportional to its frequency of occurrence in $$$A_i$$$.
    • Append the selected integer to the end of $$$b$$$.

Find the expected value of $$$f(b,T)$$$, modulo $$$998244353$$$.

Input

The first line of each test contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 10^4$$$, $$$2 \le m \le 30$$$, $$$m$$$ is even) — the size of $$$T$$$ and the number of arrays.

The second line contains $$$n$$$ distinct integers $$$T_1,T_2,\ldots,T_n$$$ ($$$0 \le T_i \le 2 \cdot 10^4$$$) — the elements of $$$T$$$.

The $$$2i-1$$$-th line of the next $$$2m$$$ lines contains an integer $$$k_i$$$ ($$$1 \le k_i \le 10^4$$$) — the size of $$$A_i$$$.

The $$$2i$$$-th line contains $$$k_i$$$ integers $$$A_{i,1},A_{i,2},\ldots,A_{i,k_i}$$$ ($$$0 \le A_{i,j} \le 10^4$$$) — the elements of $$$A_i$$$.

Output

Output an integer indicating the expected value of $$$f(b,T)$$$ modulo $$$998244353$$$. Formally, let $$$M=998244353$$$. It can be shown that the answer can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \ne 0$$$. Output $$$p \cdot q ^{-1} \bmod M$$$, where $$$q^{-1}$$$ denotes the multiplicative inverse of $$$q$$$ modulo $$$M$$$.

Examples
Input
1 2
0
2
0 1
2
0 1
Output
499122177
Input
3 4
2 3 4
3
0 2 2
5
1 2 1 1 1
1
1
2
0 3
Output
798595492