Alphabetomials (Small)

Polynomials of degree 4 and polynomials of degree 5 behave very differently. The absence of a closed formula for the roots of a general degree 5 polynomial is what produced Galois theory, which has nothing to do with this problem.

Here we only consider multi-variable polynomials of degree at most 4 over 26 variables, one variable per lowercase English letter. Here is one such polynomial:

aber+aab+c

Given a string $S$, evaluate the polynomial on it: substitute each variable with the number of times that letter appears in $S$. The result is $p(S)$.

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

p(S) = 6 * 2 * 1 * 3 + 6 * 6 * 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 every $S_i$ is a word of the dictionary. That is, $S$ is $d$ dictionary words joined by single spaces. The same word may be used more than once, and two phrases that place the words in a different order count as different.

You are given an integer $K$. For every $d$ with $1 \le d \le K$, compute the sum of $p(S)$ over all $d$-phrases. The answers can be large, so print each of them modulo 10009.

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

• One line with the polynomial $p$, then a space, then an integer $K$.
• One line with the number of words in the dictionary, $n$.
• Then $n$ lines, each with one word made of lowercase letters only. No word appears twice in the same test case.

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

Limits

• $1 \le T \le 100$
• $p$ is one or more terms joined by +. It does not start or end 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, consists of lowercase English letters only, and is at most 50 characters long.
• $1 \le n \le 20$
• $1 \le K \le 5$

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 number is the sum of $p(S)$ over all $i$-phrases, taken modulo 10009.