알파베토미얼 (큰 입력)

변수 26개를 쓰는 4차 이하 다변수 다항식만 다룬다. 변수는 영어 소문자 26개가 하나씩 맡는다. 다음은 그런 다항식의 예다.

aber+aab+c

문자열 $S$가 주어지면 이 다항식에 값을 대입해 계산한다. 각 변수 자리에는 그 문자가 $S$에 나타난 횟수를 넣고, 그 결과를 $p(S)$라고 쓴다.

예를 들어 위 다항식에 $S$ = abracadabra edgar를 넣어 보자. a는 여섯 번, b는 두 번, c는 한 번, e는 한 번, r은 세 번 나오므로

$p(S) = 6 \times 2 \times 1 \times 3 + 6 \times 6 \times 2 + 1 = 109$

이다.

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

S = "S1 S2 S3 ... Sd"

꼴이고 각 $S_i$가 사전에 있는 단어이면 $S$를 $d$-구절이라고 부른다. 즉 사전의 단어 $d$개를 공백 하나로 이어 붙인 문자열이며, 같은 단어를 여러 번 써도 된다. $K \le 10$인 $K$가 주어질 때, $1 \le d \le K$인 모든 $d$에 대해 모든 $d$-구절에 걸친 $p(S)$의 합을 구하라. 합이 커지므로 각 합을 10009로 나눈 나머지를 출력한다.

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

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

다항식은 항의 합으로 쓰고, 각 항은 변수의 곱이다. $a^t$는 문자 a를 $t$개 이어 붙여 쓴다. 예를 들어 $a^2b$는 aab로 쓴다. 한 항 안의 변수는 항상 사전순 비내림차순이다.

제한

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

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

Case #X: sum1 sum2 ... sumK

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