题目描述

给定正整数 $N$、$M$、$K$ 以及长度为 $M$ 的非负整数序列 $A = (A_0, A_1, \dots, A_{M-1})$，满足 $2^{N-1} \leq K < 2^N$。

在输入中，$K$ 以二进制表示为 $N$ 位的数字，其他整数以十进制表示。

另外，序列 $A$ 并未直接给出，而是通过以下方式描述：对于每个 $i=0, 1, \ldots, 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$。

我们的目标是计算由以下规律构成的长度为 $MK$ 的序列 $B = (B_0, B_1, \dots, B_{MK-1})$ 的逆序对数，并输出该值对 $998244353$ 取模的结果。

• 对于任意 $0 \leq a < K$ 和任意 $0 \leq b < M$，有：
  • $B_{aM+b}$ 等于 $\operatorname{popcount}(a \operatorname{AND} A_b)$ 除以 $2$ 的余数。

其中，按位与运算符 $\operatorname{AND}$ 是怎样运算的？对整数 $A$ 和 $B$，其按位与运算 $A \operatorname{AND} B$ 在二进制表示下的第 $2^k$ 位（$k \geq 0$）的值，当且仅当 $A$ 和 $B$ 在该位上均为 $1$ 时为 $1$，否则为 $0$。

例如，$3 \operatorname{AND} 5 = 1$（二进制表示为 $011 \operatorname{AND} 101 = 001$）。不论先后顺序，多个整数按位与的结果是稳定的，可表达为 $(((p\_1 \operatorname{AND} p\_2) \operatorname{AND} \cdots) \operatorname{AND} p\_k)$。

同时，$\operatorname{popcount}$ 函数作用于非负整数 $x$，返回其二进制表示中 $1$ 的总个数。具体来说，假设 $x = \sum_{i=0}^\infty b_i 2^i$，则 $\operatorname{popcount}(x) = \sum_{i=0}^\infty b_i$。举例来说，$13$ 在二进制下是 1101，因此 $\operatorname{popcount}(13) = 3$。

输入格式

从标准输入读取，格式如下：

$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}$ $\ldots$ $L_{M-1}$ $X_{M-1,0}$ $X_{M-1,1}$ $\cdots$ $X_{M-1,L_{M-1}-1}$

输出格式

输出计算得到的逆序对数结果对 $998244353$ 取模的值。

样例 1

输入

2 4
11
1 0
2 0 1
0
1 1

输出

9

样例 2

输入

3 3
101
2 1 2
2 0 1
1 0

输出

23

样例 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

输出

97754354

样例 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

输出

291412708

说明/提示

• $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$
• 所有输入都是整数
• $K$ 已经用二进制表示
• 除 $K$ 以外其他数以十进制表示

请输出对 $998244353$ 取模的逆序对数量。

本翻译由 AI 自动生成