SP7558 HAALPHA - D - Alphabetomials

**Alphabetomials** As we all know, there is a big difference between polynomials of degree 4 and those of degree 5. The question of the non-existence of a closed formula for the roots of general degree 5 polynomials produced the famous Galois theory, which, as far as the author sees, bears no relation to our problem here. We consider only the multi-variable polynomials of degree up to 4, over 26 variables, represented by the set of 26 lowercase English letters. Here is one such polynomial: ``` aber+aab+c ``` Given a string _s_, we evaluate the polynomial on it. The evaluation gives _p_(_S_) as follows: Each variable is substituted with the number of appearances of that letter in _S_. For example, take the polynomial above, and let _S_ = "abracadabra edgar". There are 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. ``` Given a dictionary of distinct words that consist of only lower case letters, we call a string _S_ a _d-phrase_ if ``` S = "S1 S2 S3 ... Sd", ``` where S $ _{i} $ is any word in the dictionary, for 1 S is in the form of _d_ dictionary words separated with spaces. Given a number **K** d K, to compute the sum of _p_(_S_) over all the _d_-phrases. Since the answers might be big, you are asked to compute the remainder when the answer is divided by 10009. Input The first line contains the number of cases **T**. **T** test cases follow. The format of each test case is: A line containing an expression _p_ for the multi-variable polynomial, as described below in this section, then a space, then follows an integer **K**. A line with an integer **n**, the number of words in the dictionary. Then **n** lines, each with a word, consists of only lower case letters. No word will be repeated in the same test case. We always write a polynomial in the form of a sum of terms; each term is a product of variables. We write _a_ $ ^{t} $ simply as _t_ _a_'s concatenated together. For example, _a_ $ ^{2} $ _b_ is written as _aab_. Variables in each term are always lexicographically non-decreasing. Output For each test case, output a single line in the form ``` Case #X: sum1 sum2 ... sumK ``` where _X_ is the case number starting from 1, and sum $ _{i} $ is the sum of _p_(_S_), where _S_ ranges over all i-phrases, modulo 10009. Limits 1 T The string _p_ consists of one or more terms joined by '+'. It will not start nor end with a '+'. There will be at most 5 terms for each _p_. Each term consists at least 1 and at most 4 lower case letters, sorted in non-decreasing order. No two terms in the same polynomial will be the same. Each word is non-empty, consists only of lower case English letters, and will not be longer than 50 characters. No word will be repeated in the same dictionary. Small dataset 1 n 1 K Large dataset 1 n 1 K Sample Input Output ` 2

ehw+hwww 5

6

where

when

what

whether

who

whose

a+e+i+o+u 3

4

apple

orange

watermelon

banana



` ` Case #1: 15 1032 7522 6864 253

Case #2: 12 96 576

`

N/A

N/A