C. Кубворд
ограничение по времени на тест
1.7 секунд
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Кубворд — особый вид кроссворда. Для построения кубворда сначала выбирается положительное целое число $$$a$$$ — длина стороны куба. Затем строится большой куб, состоящий из $$$a \times a \times a$$$ единичных кубиков. У большого куба 12 ребер. После этого выкидываются все единичные кубики, которые не касаются ребер большого куба. Рисунок ниже показывает, что получится при $$$a=6$$$.

Наконец, вы пишете по одной букве в каждый единичный кубик. Вдоль каждого ребра большого куба должно получиться осмысленное слово. Буквы на любом ребре могут быть прочитаны в любом направлении, и достаточно, чтобы хотя бы в одном из направлений получилось осмысленное слово.

Рисунок ниже показывает фигуру при $$$a=6$$$, где в некоторые единичные кубики уже записаны буквы. Уже можно прочитать слова «SUBMIT», «ACCEPT» и «TURING» вдоль трех ребер большого куба.

Вам дан список осмысленных слов. Каждое слово из этого списка может сколько угодно раз читаться на ребрах кубворда. Найдите число различных кубвордов, которые можно составить из этих слов, по модулю $$$998,244,353$$$.

Если один кубворд может быть получен из другого поворотом или отражением, они считаются различными.

Входные данные

Первая строка содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 100,000$$$) – количество слов.

Далее следуют $$$n$$$ строк. Каждая из этих строк содержит одно слово, которое может присутствовать на ребрах большого куба. Длина каждого слова находится в пределах от 3 до 10 включительно.

Гарантируется, что все слова различны.

Выходные данные

Выведите одно целое число — количество различных кубвордов из данных слов по модулю $$$998,244,353$$$.

Система оценки

Подзадача 1 (21 балл): слова содержат только буквы «a» - «f» (строчные)

Подзадача 2 (29 баллов): слова содержат только буквы «a» - «p» (строчные)

Подзадача 3 (34 балла): слова содержат только буквы «a» - «p» (строчные) и «A» - «P» (заглавные)

Подзадача 4 (16 баллов): слова содержат только буквы «a» - «z» (строчные), «A» - «Z» (заглавные) и цифры «0» - «9»

Примеры
Входные данные
1
radar
Выходные данные
1
Входные данные
1
robot
Выходные данные
2
Входные данные
2
FLOW
WOLF
Выходные данные
2
Входные данные
2
baobab
bob
Выходные данные
4097
Входные данные
3
TURING
SUBMIT
ACCEPT
Выходные данные
162
Входные данные
3
MAN1LA
MAN6OS
AN4NAS
Выходные данные
114
Примечание

В первом примере единственная возможность составить кубворд — написать слово «radar» на всех ребрах.

Во втором примере есть два различных кубворда, которые получаются друг из друга поворотом: слово «robot» на всех ребрах, и разница лишь в том, содержит ли левый нижний передний угол букву «r» или «t».

Третий пример похож на второй. То, что мы можем читать слова в обоих направлениях, не изменяет ответ.

В четвертом примере есть один кубворд со словом «bob» на каждом ребре. Кроме того, есть $$$2^{12} = 4096$$$ кубов со словом «baobab» на каждом ребре: для каждого из 12 ребер есть два возможных направления, в которых можно написать слово «baobab».