SP7558 HAALPHA - D - Alphabetomials

众所周知，4次多项式和5次多项式之间存在很大差异。广义5次多项式根的闭式不存在的问题产生了著名的伽罗瓦理论，据作者所见，该理论与我们这里的问题无关。 我们只考虑由26个小写英文字母组成的集合表示的26个变量上的4次多变量多项式。这里有一个这样的多项式： ``` aber+aab+c ``` 给定一个字符串 $s$ ，我们对其进行多项式求值。求值给出 $p(s)$ 如下：每个变量都被替换为该字母在 $s$ 中的出现次数。 例如，取上述多项式，设 $S=“abracadabra edgar”$ 。有 $6$ 个 $a$ ，$2$ 个 $b$，$1$ 个 $c$ ，$1$ 个 $e$ 和 $3$ 个 $r$ 。 ``` p[S] = 6 * 2 * 1 * 3 + 6 * 6 * 2 + 1 = 109. ``` 给定一个只由小写字母组成的字符串 $S$ ，如果 ``` S = "S1 S2 S3 ... Sd", ``` 其中 $S_i$ 是字符串中的单词，因为 $S$ 是用空格分隔的 $d$ 个单词的形式。给定一个数 $d$，计算所有 $d$ 短语上的 $p(S)$ 之和。由于答案可能很大，因此要求您将答案 $mod \ 10009$ 。

第一行：一个整数 $T$ 表示测试点数量。 对于每个测试点： 第一行：一个多变量多项式的表达式 $p$ ，如上文所述，还有一个整数 $K$ ， 中间用一个空格隔开。 第二行：一个整数 $n$ ，即字符串中的单词数。 接下来 $n$ 行，每行一个由小写字母组成的单词。同一测试点中不会重复任何单词。

对于每个测试点，输出一行 ``` Case #X: sum1 sum2 ... sumK ``` 其中 $X$ 是从 $1$ 开始的编号, $sum_i$ 是 $p(S)$ 的和，由于答案可能很大，因此要求您将答案 $mod \ 10009$ 。

字符串 $p$ 由一个或多个由 $“+”$ 连接的项组成。它不会以 $“+”$ 开头或结尾。每个 $p$ 中最多有 $5$ 个单词。每个单词至少由 $1$ 个小写字母构成，最多由 $4$ 个小写字母构成，按非降序排列。同一多项式中没有两个项是相同的。 数据保证每个单词不为空，且仅由小写英文字母组成，长度不超过 $50$ 个字符。同一字符串中不会重复任何单词。