알파벳다항식

우리 모두가 알다시피, 차수가 4인 다항식과 차수가 5인 다항식 사이에는 큰 차이가 있다. 일반적인 차수 5 다항식의 근에 대한 닫힌 공식이 존재하지 않는다는 문제로부터 유명한 Galois 이론이 탄생했지만, 저자가 보기에 이는 여기서 다루는 문제와 아무런 관련이 없다.

여기서는 26개의 소문자 영어 알파벳으로 나타내는 26개의 변수에 대한, 차수가 최대 4인 다변수 다항식만 고려한다. 다음은 그러한 다항식의 한 예이다.

aber+aab+c

문자열 s가 주어지면 이 문자열에 대해 다항식을 계산한다. p(S)의 값은 다음과 같이 구한다. 각 변수에 S에서 해당 문자가 등장하는 횟수를 대입한다. 예를 들어 위의 다항식을 사용하고 S = "abracadabra edgar"라고 하자. a는 여섯 번, b는 두 번, c는 한 번, e는 한 번, r은 세 번 등장한다. 따라서

p(S) = 6 * 2 * 1 * 3 + 6 * 6 * 2 + 1 = 109.

소문자만으로 이루어진 서로 다른 단어들의 사전이 주어질 때, 문자열 S가 다음을 만족하면 이를 d-구문이라고 부른다.

S = "S_{1} S_{2} S_{3} ... S_{d}",

여기서 1 ≤ i ≤ d인 각 i에 대해 $S_{i}$는 사전에 있는 임의의 단어이다. 즉, S는 사전의 단어 d개를 공백으로 구분한 형태이다. 수 K ≤ 10이 주어질 때, 각 1≤ d ≤ K에 대해 모든 d-구문에 대한 p(S)의 합을 계산해야 한다. 답이 클 수 있으므로, 답을 10009으로 나눈 나머지를 계산한다.

제한

메모리 제한: 1 GB. 1 ≤ T ≤ 100. 문자열 p는 하나 이상의 항을 '+'로 연결한 형태이다. '+'로 시작하거나 끝나지 않는다. 각 p에는 최대 5개의 항이 있다. 각 항은 적어도 1개, 최대 4개의 소문자로 이루어지며, 비내림차순으로 정렬되어 있다. 같은 다항식 안에서 동일한 두 항은 존재하지 않는다. 각 단어는 비어 있지 않고 소문자 영어 알파벳으로만 이루어지며, 길이는 50자를 넘지 않는다. 같은 사전에서 동일한 단어가 반복되지 않는다.

소규모 데이터 세트

시간 제한: 30초. 1 ≤ n ≤ 20 1 ≤ K ≤ 5

대규모 데이터 세트

시간 제한: 60초. 1 ≤ n ≤ 100 1 ≤ K ≤ 10

첫째 줄에 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스의 형식은 다음과 같다. 이 절의 아래에서 설명하는 다변수 다항식의 식 p가 한 줄에 주어지고, 그 뒤에 공백 하나와 정수 K가 주어진다. 다음 줄에 사전에 있는 단어의 수를 나타내는 정수 n이 주어진다. 이어지는 n개의 줄에는 소문자만으로 이루어진 단어가 하나씩 주어진다. 같은 테스트 케이스에서 동일한 단어가 반복되지 않는다.

다항식은 항상 항들의 합 형태로 쓰며, 각 항은 변수들의 곱이다. $a^{t}$은 단순히 a를 t개 이어 붙여 쓴다. 예를 들어 $a^{2}$b는 에이에이비라고 쓴다. 각 항의 변수는 항상 사전순으로 비내림차순이다.

각 테스트 케이스마다 다음 형식으로 한 줄을 출력한다.

Case #X: sum_{1} sum_{2} ... sum_{K}

여기서 X는 1부터 시작하는 케이스 번호이고, $sum_{i}$은 모든 i-구문을 범위로 하는 S에 대한 p(S)의 합을 10009로 나눈 나머지이다.