Alphabetomials (Large)

We work only with multi-variable polynomials of degree at most 4 over 26 variables, one variable for each lowercase English letter. Here is one such polynomial:

aber+aab+c

Given a string $S$, evaluate the polynomial on it. Every variable is replaced by the number of times that letter appears in $S$, and the result is called $p(S)$.

For example, take the polynomial above and let $S$ be abracadabra edgar. It contains six a's, two b's, one c, one e, and three r's, so

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

You are given a dictionary of distinct words made of lowercase letters only. A string $S$ is a $d$-phrase if

S = "S1 S2 S3 ... Sd"

where each $S_i$ is a word from the dictionary. That is, $S$ is $d$ dictionary words joined by single spaces, and the same word may be used more than once. Given $K$ with $K \le 10$, compute the sum of $p(S)$ over all $d$-phrases, for every $d$ with $1 \le d \le K$. The sums get large, so report each one modulo 10009.

The first line contains the number of test cases $T$. Each test case has this format:

• a line with an expression $p$ for the polynomial, then one space, then an integer $K$;
• a line with an integer $n$, the number of words in the dictionary;
• $n$ lines, each holding one word made of lowercase letters only. No word repeats inside one test case.

A polynomial is always written as a sum of terms, and each term is a product of variables. $a^t$ is written as $t$ copies of the letter a concatenated, so $a^2b$ is written as aab. The variables inside a term are always in non-decreasing lexicographic order.

Constraints

• $1 \le T \le 100$
• $p$ is one or more terms joined by +, and it neither starts nor ends with +. Each $p$ has at most 5 terms. Each term has at least 1 and at most 4 lowercase letters in non-decreasing order. No two terms of one polynomial are equal.
• Each word is non-empty, uses only lowercase English letters, and is at most 50 characters long. No word repeats inside one dictionary.
• $1 \le n \le 100$
• $1 \le K \le 10$

For each test case, print a single line in the form

Case #X: sum1 sum2 ... sumK

where $X$ is the case number starting from 1, and the $i$-th value is the sum of $p(S)$ over all $i$-phrases, taken modulo 10009.