У Васи есть набор из 4n строк одинаковой длины, состоящих только из строчных латинских букв «a», «b», «c», «d» и «e», причем они разбиты на n групп по 4 одинаковые строки. У Васи также есть одна особая строка a той же длины, состоящая только из букв «a».
Вася хочет получить из строки a некоторую заданную строку b, для этого он может использовать имеющиеся у него строки в любом порядке. При использовании некоторой строки x каждый из символов строки a заменяется на следующий в алфавите столько раз, каким по счету в алфавите является соответствующий символ строки x, считая с нуля. При этом следующей для буквы «e» является буква «a».
Например, если некоторая буква строки a равна «b», а буква на той же позиции строки x равна «c», то буква строки a становится равной «d», так как «c» — второй символ алфавита, считая с нуля. Если же в строке a была буква «e», а в строке x — «d», то буква в строке a заменится на «c». Например, если строка a была равна «abcde», а строка x — «baddc», то строка a станет равной «bbabb».
После использовании строки она исчезает, но Вася может несколько раз использовать равные строки.
Васю интересует для q заданных строк b, сколько существует способов получить из строки a строку b заданным набором из 4n строк? Два способа считаются различными, если количество строк, использованных из какой-то группы из 4 строк, различно. Помогите Васе, посчитайте ответы на эти вопросы по модулю 109 + 7.
Выходные данные
Для каждой интересной Васе строки выведите количество способов получить ее из строки a по модулю 109 + 7.
Примечание
Пояснение к первому примеру. У Васи есть 4 строки «b». Тогда существует единственный способ для каждой строки b: выбрать 0 строк «b» и получить строку «a», и выбрать 4 строки «b» и получить строку «e», соответственно. Получаем, что у нас по 1 способу для каждого запроса.
Пояснение ко второму тесту. Заметим, что выбор строки «aaaa» ничего не меняет, то есть ее мы можем выбрать любое их количество от 0 до 4, т.е. 5 разных способов, а выбрать строку «bbbb» мы должны только 2 раза, так как другие варианты не подходят. Получаем, что у нас 5 способов для единственного запроса.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1 1
b
2
a
e
|
1
1
|
|
2
|
2 4
aaaa
bbbb
1
cccc
|
5
|