Vasya and Shifts

Vasya에게는 길이가 같고 영문 소문자 "a", "b", "c", "d", "e"로 이루어진 4n개의 문자열로 구성된 집합이 있다. 또한 이 집합은 각각 동일한 문자열 4개로 이루어진 n개의 그룹으로 나뉜다. Vasya에게는 길이가 같고 문자 "a"만으로 이루어진 특별한 문자열 a도 하나 있다.

Vasya는 문자열 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"가 된다.

사용한 문자열은 사라지지만, Vasya는 서로 같은 문자열을 여러 번 사용할 수 있다.

Vasya는 주어진 q개의 문자열 b 각각에 대해, 주어진 4n개의 문자열 집합을 사용하여 문자열 a로부터 문자열 b를 얻는 방법의 수를 알고자 한다. 어떤 4개 문자열 그룹에서 사용한 문자열의 개수가 다르면 두 방법은 서로 다르다. Help Vasya 이 질문들의 답을 109 + 7로 나눈 나머지를 계산한다.

첫 번째 줄에는 두 정수 n와 m (1 ≤ n, m ≤ 500)이 주어진다. 이는 각각 집합에 있는 네 문자열 그룹의 수와 모든 문자열의 길이이다.

다음 n개의 각 줄에는 길이가 m이고 영문 소문자 "a", "b", "c", "d", "e"로 이루어진 문자열 s가 주어진다. 이는 s와 같은 문자열 네 개로 이루어진 그룹이 하나 있음을 뜻한다.

다음 줄에는 Vasya가 관심 있는 문자열 b의 개수를 나타내는 정수 하나 q (1 ≤ q ≤ 300)이 주어진다.

다음 q개의 각 줄에는 길이가 m이고 영문 소문자 "a", "b", "c", "d", "e"로 이루어진 문자열 b가 주어진다. 이는 Vasya가 관심 있는 문자열이다.

Vasya가 관심 있는 각 문자열에 대해, 문자열 a로부터 그 문자열을 얻는 방법의 수를 109 + 7로 나눈 나머지를 출력한다.

첫 번째 예제에는 문자열 "b"가 4개 있다. 각 문자열 b를 얻는 방법은 유일하다. 각각 "a"를 얻으려면 문자열 "b"를 0개 선택하고, "e"를 얻으려면 문자열 "b"를 4개 선택한다. 따라서 각 요청마다 방법이 1개 있다.

두 번째 예제에서는 문자열 "aaaa"의 선택은 아무것도 바꾸지 않는다는 점에 유의한다. 즉, 이 문자열을 0개부터 4개까지 원하는 개수만큼 선택할 수 있으며, 이는 5개의 서로 다른 방법이다. 그리고 다른 경우는 조건에 맞지 않으므로 문자열 "bbbb"을 2번 선택해야 한다. 따라서 이 요청에 대한 방법은 5개이다.