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

У Васи есть набор из 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.

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

В первой строке через пробел записаны два целых числа: n и m (1 ≤ n, m ≤ 500) — количество четверок строк в наборе, и длина каждой из них.

В каждой из следующих n строк находится строка s длины m, состоящая только из строчных латинских букв «a», «b», «c», «d» и «e». Это означает, что очередная четверка строк в наборе Васи равна строке s.

В следующей строке находится одно целое число q (1 ≤ q ≤ 300) — количество строк b, интересных Васе.

В каждой из следующих q строк находится строка b длины m, состоящая только из строчных латинских букв «a», «b», «c», «d» и «e» — строка, интересующая Васю.

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

Для каждой интересной Васе строки выведите количество способов получить ее из строки a по модулю 109 + 7.

Примеры
Входные данные
1 1
b
2
a
e
Выходные данные
1
1
Входные данные
2 4
aaaa
bbbb
1
cccc
Выходные данные
5
Примечание

Пояснение к первому примеру. У Васи есть 4 строки «b». Тогда существует единственный способ для каждой строки b: выбрать 0 строк «b» и получить строку «a», и выбрать 4 строки «b» и получить строку «e», соответственно. Получаем, что у нас по 1 способу для каждого запроса.

Пояснение ко второму тесту. Заметим, что выбор строки «aaaa» ничего не меняет, то есть ее мы можем выбрать любое их количество от 0 до 4, т.е. 5 разных способов, а выбрать строку «bbbb» мы должны только 2 раза, так как другие варианты не подходят. Получаем, что у нас 5 способов для единственного запроса.