알파벳 다항식 (Small)

차수가 4인 다항식과 5인 다항식은 성질이 크게 다르다. 일반적인 5차 다항식의 근을 구하는 닫힌 공식이 없다는 사실에서 갈루아 이론이 나왔지만, 이 문제와는 아무 상관이 없다.

여기서는 소문자 알파벳 26개를 변수로 쓰는 차수 4 이하의 다변수 다항식만 다룬다. 다음은 그런 다항식의 예다.

aber+aab+c

문자열 $S$가 주어지면 각 변수에 그 문자가 $S$에 나타나는 횟수를 대입해서 다항식의 값 $p(S)$를 구한다.

예를 들어 위 다항식에 $S$ = abracadabra edgar를 대입한다. a는 여섯 번, b는 두 번, c는 한 번, e는 한 번, r은 세 번 나오므로 값은 다음과 같다.

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

서로 다른 소문자 단어로 이루어진 사전이 주어진다. 문자열 $S$가

S = S1 S2 S3 ... Sd

꼴이고 각 $S_i$가 사전에 있는 단어이면 $S$를 $d$-구절이라고 부른다. 즉 사전의 단어 $d$개를 공백 하나로 이어 붙인 문자열이다. 같은 단어를 여러 번 써도 되고, 단어를 놓는 순서가 다르면 서로 다른 구절로 센다.

정수 $K$가 주어진다. $1 \le d \le K$인 각 $d$에 대해 모든 $d$-구절의 $p(S)$ 합을 구하라. 답이 커질 수 있으므로 10009로 나눈 나머지를 출력한다.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스의 형식은 다음과 같다.

• 첫 줄에 다항식 $p$, 공백, 정수 $K$가 차례로 주어진다.
• 다음 줄에 사전에 있는 단어의 개수 $n$이 주어진다.
• 다음 $n$개 줄에 소문자로만 이루어진 단어가 한 줄에 하나씩 주어진다. 한 테스트 케이스 안에서 같은 단어가 두 번 나오지 않는다.

다항식은 항의 합으로 적고, 각 항은 변수의 곱이다. $a^t$는 a를 $t$개 이어 붙여 적는다. 예를 들어 $a^2 b$는 aab로 적는다. 한 항 안의 변수는 항상 사전순으로 감소하지 않게 적혀 있다.

제한

• $1 \le T \le 100$
• $p$는 +로 이어진 항 하나 이상으로 이루어지고, +로 시작하거나 끝나지 않는다. 한 다항식의 항은 최대 5개다. 각 항은 사전순으로 감소하지 않는 소문자 1개 이상 4개 이하로 이루어진다. 한 다항식 안에 같은 항이 두 번 나오지 않는다.
• 각 단어는 비어 있지 않고, 소문자로만 이루어지며, 길이가 50 이하다.
• $1 \le n \le 20$
• $1 \le K \le 5$

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

Case #X: sum1 sum2 ... sumK

$X$는 1부터 시작하는 테스트 케이스 번호이고, $i$번째 수는 모든 $i$-구절에 대한 $p(S)$의 합을 10009로 나눈 나머지다.