对于字符串序列 $$$[t_1, t_2, \dots, t_m]$$$,我们将函数 $$$f([t_1, t_2, \dots, t_m])$$$ 定义为至少一个字符串 $$$t_i$$$ 的子序列的不同字符串(包括空字符串)的数量。 $$$f([]) = 0$$$ (即空序列中此类字符串的数量为 $$$0$$$)。
给定一个字符串序列 $$$[s_1, s_2, \dots, s_n]$$$。该序列中的每个字符串都由小写拉丁字母组成,并且经过排序(即,每个字符串以几个(可能为零)字符 a 开头,然后是几个(可能为零)字符 b,...,以几个(可能零)字符 z 结尾)。
对于 $$$[s_1, s_2, \dots, s_n]$$$ 的每个 $$$2^n$$$ 子序列,计算函数 $$$f$$$ 模 $$$998244353$$$ 的值。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 23$$$) — 字符串的数量。
然后是 $$$n$$$ 行。第 $$$i$$$ 行包含字符串 $$$s_i$$$ ($$$1 \le |s_i| \le 2 \cdot 10^4$$$),由小写拉丁字母组成。每个字符串 $$$s_i$$$ 均已排序。
输出
由于打印最多 $$$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$$$)。
示例
输入 #1
3 a b c
输出 #1
92
输入 #2
2 aa a
输出 #2
21
输入 #3
2 a a
输出 #3
10
输入#4
2 abcd aabb
输出#4
124
输入 #5
3 ddd aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaabbbbbbbbbbbcccccccccccciiiiiiiiiiiiiiiiiiiiiiooooooooooqqqqqqqqqqqqqqqqqqvvvvvzzzzzzzzzzzz
输出 #5
15706243380