E. Типичная вечеринка в общаге
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Сегодня в общаге праздник  — приехал Олег, в честь чего девочки подарили ему строку. Олегу очень понравился подарок, поэтому он тут же придумал и предложил вам, лучшему его другу, следующую задачу.

Вам дана строка $$$s$$$ длины $$$n$$$, которая состоит из первых $$$17$$$ строчных букв латинского алфавита {$$$a$$$, $$$b$$$, $$$c$$$, $$$\ldots$$$, $$$p$$$, $$$q$$$} и знаков вопроса. А также $$$q$$$ запросов. Каждый запрос характеризуется набором попарно различных строчных первых $$$17$$$ букв латинского алфавита, которые можно использовать чтобы заменить знаки вопроса в строке $$$s$$$.

Ответом на запрос является сумма количества различных подстрок, которые являются палиндромами, по всем строкам, которые можно получить из изначальной строки $$$s$$$ путем замены знаков вопроса на разрешенные символы. Ответ необходимо посчитать по модулю $$$998\,244\,353$$$.

Обратите внимание! Две подстроки являются различными, когда отличаются их позиции начала и окончания в строке. Т. е. количество различных подстрок, которые являются палиндромами, для строки aba будет $$$4$$$: a, b, a, aba.

Рассмотрим примеры замены знаков вопроса на буквы. Например, из строки aba??ee при запросе {$$$a$$$, $$$b$$$} можно получить строки ababaee или abaaaee но нельзя получить строки pizza, abaee, abacaba, aba?fee, aba47ee, или abatree.

Напомним, что палиндромом называется строка, которая одинаково читается как слева направо, так и справа налево.

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

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

Вторая строка содержит строку $$$s$$$, которая состоит из $$$n$$$ строчных букв латинского алфавита и знаков вопроса. Гарантируется, что все буквы в строке принадлежат множеству {$$$a$$$, $$$b$$$, $$$c$$$, $$$\ldots$$$, $$$p$$$, $$$q$$$}.

Третья строка содержит одно целое число $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — количество запросов.

Далее следуют $$$q$$$ строк в каждой из которых содержится единственная строка $$$t$$$ — набор символов, которыми можно заменять знаки вопроса ($$$1 \le |t| \le 17$$$). Гарантируется, что все буквы в строке принадлежат множеству {$$$a$$$, $$$b$$$, $$$c$$$, $$$\ldots$$$, $$$p$$$, $$$q$$$} и встречаются не более одного раза.

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

На каждый запрос выведите одно число — суммарное количество подстрок-палиндромов во всех возможных строках, которые можно получить из строки $$$s$$$, по модулю $$$998\,244\,353$$$.

Примеры
Входные данные
7
ab??aba
8
a
b
ab
abc
abcd
abcde
abcdef
abcdefg
Выходные данные
14
13
55
105
171
253
351
465
Входные данные
11
???????????
6
abcdefghijklmnopq
ecpnkhbmlidgfjao
olehfan
codef
glhf
q
Выходные данные
900057460
712815817
839861037
756843750
70840320
66
Примечание

Рассмотрим первый пример и первый запрос в нём. У нас может получится только одна строка по итогам замены знаков вопроса  — abaaaba. В ней есть такие подстроки-палиндромы:

  1. a  — подстрока [$$$1$$$; $$$1$$$].
  2. b  — подстрока [$$$2$$$; $$$2$$$].
  3. a  — подстрока [$$$3$$$; $$$3$$$].
  4. a  — подстрока [$$$4$$$; $$$4$$$].
  5. a  — подстрока [$$$5$$$; $$$5$$$].
  6. b  — подстрока [$$$6$$$; $$$6$$$].
  7. a  — подстрока [$$$7$$$; $$$7$$$].
  8. aa  — подстрока [$$$3$$$; $$$4$$$].
  9. aa  — подстрока [$$$4$$$; $$$5$$$].
  10. aba  — подстрока [$$$1$$$; $$$3$$$].
  11. aaa  — подстрока [$$$3$$$; $$$5$$$].
  12. aba  — подстрока [$$$5$$$; $$$7$$$].
  13. baaab  — подстрока [$$$2$$$; $$$6$$$].
  14. abaaaba  — подстрока [$$$1$$$; $$$7$$$].

В третьем запросе у нас может получится 4 строки: abaaaba, abababa, abbaaba, abbbaba.