G. Подпоследовательности повсюду
ограничение по времени на тест
10 секунд
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Для последовательности строк $$$[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).

Для каждой из $$$2^n$$$ подпоследовательностей $$$[s_1, s_2, \dots, s_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)$$$. Выведите XOR всех $$$2^n$$$ чисел, которые у вас получатся.

Индексы $$$i_1, i_2, \dots, i_k$$$ в описании подпоследовательности заданы в $$$1$$$-индексации (то есть они от $$$1$$$ до $$$n$$$).

Примеры
Входные данные
3
a
b
c
Выходные данные
92
Входные данные
2
aa
a
Выходные данные
21
Входные данные
2
a
a
Выходные данные
10
Входные данные
2
abcd
aabb
Выходные данные
124
Входные данные
3
ddd
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaabbbbbbbbbbbcccccccccccciiiiiiiiiiiiiiiiiiiiiiooooooooooqqqqqqqqqqqqqqqqqqvvvvvzzzzzzzzzzzz
Выходные данные
15706243380