众所周知，4 次多项式与 5 次多项式之间存在巨大差异。关于一般 5 次多项式根的封闭公式不存在的问题，引出了著名的伽罗瓦理论，据作者所见，这与我们这里的问题无关。
我们仅考虑 26 个变量（用 26 个小写英文字母表示）的最高次数为 4 的多元多项式。以下是一个这样的多项式示例：
aber+aab+c
给定一个字符串 $S$，我们对其进行多项式求值。求值结果 $p(S)$ 的计算方式如下：每个变量被替换为该字母在 $S$ 中出现的次数。
例如，取上述多项式，令 $S = \text{"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$ 是字典中的任意单词（$1 \le i \le d$），即 $S$ 是由 $d$ 个字典单词通过空格连接而成的形式，我们称 $S$ 为一个 $d$-短语。给定一个数字 $K \le 10$，你的任务是对于每个 $1 \le d \le K$，计算所有 $d$-短语的 $p(S)$ 之和。由于答案可能很大，请计算答案对 10009 取模后的余数。
输入格式
第一行包含测试用例数量 $T$。接下来是 $T$ 个测试用例。每个测试用例的格式如下：
一行包含多元多项式表达式 $p$（格式见下文），随后是一个空格，接着是一个整数 $K$。
一行包含一个整数 $n$，表示字典中的单词数量。
接下来 $n$ 行，每行一个单词，仅由小写字母组成。同一测试用例中不会出现重复单词。
我们总是将多项式写成项之和的形式；每一项都是变量的乘积。我们将 $a^t$ 简单地写成 $t$ 个 $a$ 连接在一起。例如，$a^2b$ 写为 $aab$。每一项中的变量总是按字典序非递减排列。
输出格式
对于每个测试用例，输出一行，格式如下：
Case #X: sum1 sum2 ... sumK其中 $X$ 是从 1 开始的用例编号，$sum_i$ 是所有 $i$-短语的 $p(S)$ 之和，对 10009 取模。
数据范围
$1 \le T \le 100$。
字符串 $p$ 由一个或多个由 '+' 连接的项组成。它不会以 '+' 开头或结尾。每个 $p$ 最多有 5 项。每一项包含至少 1 个且最多 4 个小写字母，按非递减顺序排列。同一多项式中不会有相同的项。
每个单词非空，仅由小写英文字母组成，长度不超过 50 个字符。同一字典中不会有重复单词。
小数据集 (4 分)
$1 \le n \le 20$
$1 \le K \le 5$
大数据集 (20 分)
$1 \le n \le 100$
$1 \le K \le 10$
样例
样例输入 1
2 ehw+hwww 5 6 where when what whether who whose a+e+i+o+u 3 4 apple orange watermelon banana
样例输出 1
Case #1: 15 1032 7522 6864 253 Case #2: 12 96 576