Score : $1000$ points

问题陈述

给定正整数 $N$, $M$ 和 $K$，以及一个非负整数序列 $A = (A_{0}, A_{1}, \dots, A_{M-1})$。这里，满足 $2^{N - 1} \leq K < 2^{N}$。

在输入中，$K$ 以二进制形式给出，而其他整数以十进制形式给出。

此外，$A$ 不是直接在输入中给出的。相反，对于每个 $i = 0, 1, \dots, M - 1$，你将得到一个 $L_i$ 整数序列 $X_{i} = (X_{i,0}, X_{i,1}, \dots, X_{i,L_{i}-1})$，使得 $A_{i} = \sum_{j=0}^{L_{i}-1} 2^{X_{i,j}}$。这里，满足 $0 \leq X_{i,0} < X_{i,1} < \cdots < X_{i,L_{i}-1} < N$。

找到序列 $B = (B_{0}, B_{1}, \dots, B_{MK-1})$ 的逆序数，模 $998244353$，定义如下。

• 对于任何整数 $a$ 使得 $0 \leq a < K$ 和任何整数 $b$ 使得 $0 \leq b < M$，以下成立：
  • $B_{aM+b}$ 等于 $\operatorname{popcount}(a \operatorname{AND} A_{b})$ 除以 $2$ 的余数。

什么是 $\operatorname{AND}$？

整数 $A$ 和 $B$ 的按位 $\operatorname{AND}$，记作 $A \operatorname{AND} B$，定义如下：

• 在 $A \operatorname{AND} B$ 的二进制表示中，$2^k$（$k \geq 0$）位上的数字是 $1$ 当且仅当 $A$ 和 $B$ 的二进制表示中 $2^k$ 位上的数字都是 $1$；否则是 $0$。

例如，$3 \operatorname{AND} 5 = 1$（二进制：$011 \operatorname{AND} 101 = 001$）。一般来说，$k$ 个整数 $p_1, p_2, p_3, \dots, p_k$ 的按位 $\operatorname{AND}$ 定义为 $(\dots ((p_1 \operatorname{AND} p_2) \operatorname{AND} p_3) \operatorname{AND} \dots \operatorname{AND} p_k)$，可以证明这与 $p_1, p_2, p_3, \dots, p_k$ 的顺序无关。

什么是 $\operatorname{popcount}$？

对于非负整数 $x$，$\operatorname{popcount}(x)$ 是 $x$ 的二进制表示中 $1$ 的数量。更准确地说，对于非负整数 $x$ 使得 $\displaystyle x = \sum_{i=0}^{\infty} b_i 2^i\ (b_i \in {0, 1})$，满足 $\displaystyle \operatorname{popcount}(x) = \sum_{i=0}^{\infty} b_i$。例如，$13$ 是二进制中的 1101，所以 $\operatorname{popcount}(13) = 3$。

以上为大语言模型 kimi 翻译，仅供参考。

Problem Statement

You are given positive integers $N$, $M$, and $K$, and a sequence of $M$ non-negative integers $A = (A_{0}, A_{1}, \dots, A_{M-1})$. Here, $2^{N - 1} \leq K < 2^{N}$ holds.

In the input, $K$ is given as an $N$-digit number in binary notation, while the other integers are given in decimal notation.

Additionally, $A$ is not given directly in the input. Instead, for each $i = 0, 1, \dots, M - 1$, you are given a sequence of $L_i$ integers $X_{i} = (X_{i,0}, X_{i,1}, \dots, X_{i,L_{i}-1})$ such that $A_{i} = \sum_{j=0}^{L_{i}-1} 2^{X_{i,j}}$. Here, $0 \leq X_{i,0} < X_{i,1} < \cdots < X_{i,L_{i}-1} < N$ holds.

Find the inversion number, modulo $998244353$, of the sequence $B = (B_{0}, B_{1}, \dots, B_{MK-1})$ defined as follows.

• For any integer $a$ such that $0 \leq a < K$ and any integer $b$ such that $0 \leq b < M$, the following holds:
  • $B_{aM+b}$ is equal to the remainder when $\operatorname{popcount}(a \operatorname{AND} A_{b})$ is divided by $2$.

What is $\operatorname{AND}$?

The bitwise $\operatorname{AND}$ of integers $A$ and $B$, denoted as $A \operatorname{AND} B$, is defined as follows:

• In the binary representation of $A \operatorname{AND} B$, the digit at the $2^k$ ($k \geq 0$) place is $1$ if and only if the digits at the $2^k$ place in the binary representations of both $A$ and $B$ are $1$; otherwise, it is $0$.

For example, $3 \operatorname{AND} 5 = 1$ (in binary: $011 \operatorname{AND} 101 = 001$). Generally, the bitwise $\operatorname{AND}$ of $k$ integers $p_1, p_2, p_3, \dots, p_k$ is defined as $(\dots ((p_1 \operatorname{AND} p_2) \operatorname{AND} p_3) \operatorname{AND} \dots \operatorname{AND} p_k)$, and it can be proved that this is independent of the order of $p_1, p_2, p_3, \dots, p_k$.

What is $\operatorname{popcount}$?

For a non-negative integer $x$, $\operatorname{popcount}(x)$ is the number of $1$s in the binary representation of $x$. More precisely, for a non-negative integer $x$ such that $\displaystyle x = \sum_{i=0}^{\infty} b_i 2^i\ (b_i \in {0, 1})$, it holds that $\displaystyle \operatorname{popcount}(x) = \sum_{i=0}^{\infty} b_i$. For example, $13$ is 1101 in binary, so $\operatorname{popcount}(13) = 3$.

Constraints

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq M \leq 2 \times 10^5$
• $2^{N-1} \leq K < 2^{N}$
• $0 \leq L_{i} \leq N$
• $\sum L_{i} \leq 2 \times 10^5$
• $0 \leq X_{i,0} < X_{i,1} < \cdots < X_{i,L_{i}-1} < N$
• All input values are integers.
• $K$ is given in binary notation.
• All numbers except $K$ are given in decimal notation.

Input

The input is given from Standard Input in the following format:

$N$ $M$

$K$

$L_{0}$ $X_{0,0}$ $X_{0,1}$ $\cdots$ $X_{0,L_{0}-1}$

$L_{1}$ $X_{1,0}$ $X_{1,1}$ $\cdots$ $X_{1,L_{1}-1}$

$\vdots$

$L_{M-1}$ $X_{M-1,0}$ $X_{M-1,1}$ $\cdots$ $X_{M-1,L_{M-1}-1}$

Output

Print the answer.

Sample Input 1

2 4
11
1 0
2 0 1
0
1 1

Sample Output 1

9

$A = (1, 3, 0, 2), B = (0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1)$.

Sample Input 2

3 3
101
2 1 2
2 0 1
1 0

Sample Output 2

23

$A = (6, 3, 1), B = (0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0)$.

Sample Input 3

16 7
1101010000100110
11 0 1 2 3 7 10 11 12 13 14 15
7 4 6 8 10 11 12 13
6 0 1 6 8 10 12
8 0 3 5 6 10 11 12 13
10 0 1 2 3 4 5 6 8 12 13
9 3 4 5 6 8 9 11 14 15
8 0 4 7 9 10 11 13 14

Sample Output 3

97754354

Sample Input 4

92 4
10101100101111111111011101111111101011001011111110011110111111101111111110100111100010111011
23 1 2 5 13 14 20 28 32 34 39 52 56 59 60 62 64 67 69 71 78 84 87 91
20 15 17 22 28 36 40 43 47 52 53 57 67 72 77 78 81 87 89 90 91
23 7 8 9 10 11 13 16 19 22 23 30 33 42 49 51 52 58 64 71 73 76 79 83
22 1 13 19 26 27 28 29 35 39 40 41 46 55 60 62 64 67 74 79 82 89 90

Sample Output 4

291412708

Find the number modulo $998244353$.