CF1620G.Subsequences Galore

For a sequence of strings $[t_1, t_2, \dots, t_m]$, let's define the function $f([t_1, t_2, \dots, t_m])$ as the number of different strings (including the empty string) that are subsequences of at least one string $t_i$. $f([]) = 0$ (i. e. the number of such strings for an empty sequence is $0$).

You are given a sequence of strings $[s_1, s_2, \dots, s_n]$. Every string in this sequence consists of lowercase Latin letters and is sorted (i. e., each string begins with several (maybe zero) characters a, then several (maybe zero) characters b, ..., ends with several (maybe zero) characters z).

For each of $2^n$ subsequences of $[s_1, s_2, \dots, s_n]$, calculate the value of the function $f$ modulo $998244353$.

对于字符串序列 $[t_1, t_2, \dots, t_m]$，定义函数 $f([t_1, t_2, \dots, t_m])$ 为：至少是某个字符串 $t_i$ 的子序列（subsequence）的不同字符串（包括空字符串）的个数。规定 $f([]) = 0$（即空序列对应的该数值为 $0$）。

给定一个字符串序列 $[s_1, s_2, \dots, s_n]$。该序列中每个字符串均由小写拉丁字母组成，且是有序的（即每个字符串以若干个（可能为零个）字符 a 开头，接着是若干个（可能为零个）字符 b，……，最后以若干个（可能为零个）字符 z 结尾）。

对 $[s_1, s_2, \dots, s_n]$ 的全部 $2^n$ 个子序列，分别计算函数 $f$ 的值，并对 $998244353$ 取模。

The first line contains one integer $n$ ($1 \le n \le 23$) — the number of strings.

Then $n$ lines follow. The $i$-th line contains the string $s_i$ ($1 \le |s_i| \le 2 \cdot 10^4$), consisting of lowercase Latin letters. Each string $s_i$ is sorted.

第一行包含一个整数 $n$（$1 \le n \le 23$）—— 字符串的数量。

接下来是 $n$ 行。第 $i$ 行包含字符串 $s_i$（$1 \le |s_i| \le 2 \cdot 10^4$），由小写拉丁字母组成。每个字符串 $s_i$ 是已排序的。

Since printing up to $2^{23}$ integers would be really slow, you should do the following:

For each of the $2^n$ subsequences (which we denote as $[s_{i_1}, s_{i_2}, \dots, s_{i_k}]$), calculate $f([s_{i_1}, s_{i_2}, \dots, s_{i_k}])$, take it modulo $998244353$, then multiply it by $k \cdot (i_1 + i_2 + \dots + i_k)$. Print the XOR of all $2^n$ integers you get.

The indices $i_1, i_2, \dots, i_k$ in the description of each subsequences are $1$-indexed (i. e. are from $1$ to $n$).

由于输出最多 $2^{23}$ 个整数会非常慢，你需要执行以下操作：

对于全部 $2^n$ 个子序列（记为 $[s_{i_1}, s_{i_2}, \dots, s_{i_k}]$），计算 $f([s_{i_1}, s_{i_2}, \dots, s_{i_k}])$，对其结果取模 $998244353$，再乘以 $k \cdot (i_1 + i_2 + \dots + i_k)$。最后输出所得到的全部 $2^n$ 个整数的异或（XOR）值。

在每个子序列的描述中，下标 $i_1, i_2, \dots, i_k$ 采用从 1 开始的索引（即取值范围为 $1$ 到 $n$）。