P4591 [TJOI2018] 碱基序列

小豆参加了生物实验室。在实验室里，他主要研究蛋白质。他现在研究的蛋白质是由 $k$ 个氨基酸按一定顺序构成的。每一个氨基酸都可能有 $a$ 种碱基序列 $s_{i,j}$ 构成。 现在小豆有一个碱基串 $s$，小豆想知道在这个碱基上都多少种不同的组合方式可能得到这个蛋白质。即求由 $k$ 段字符串有序合并成的字符串 $s_1$，有多少种不同方式能够匹配字符串 $s$，其中 $k$ 段字符串的选法不同，或者与 $s$ 匹配上的位置不同认为是不同的方式。

无

无

### 样例 1 解释 - 第一个选 $\tt A$ 第二个选 $\tt C$，得到 $\tt AC$ 能够与 $\tt ABC$ 产生 $0$ 种匹配方式； - 第一个选 $\tt A$ 第二个选 $\tt BC$，得到 $\tt ABC$ 能够与 $\tt ABC$ 产生 $1$ 种匹配方式； - 第一个选 $\tt AB$ 第二个选 $\tt C$，得到 $\tt ABC$ 能够与 $\tt ABC$ 产生 $1$ 种匹配方式； - 第一个选 $\tt AB$ 第二个选 $\tt BC$，得到 $\tt ABBC$ 能够与 $\tt ABC$ 产生 $0$ 种匹配方式。 所以一共 $2$ 种。 ### 样例 2 解释 - 第一个选 $\tt A$ 第二个选 $\tt A$，得到 $\tt AA$ 能够与 $\tt AAA$ 产生 $2$ 种匹配方式； - 第一个选 $\tt A$ 第二个选 $\tt AA$，得到 $\tt AAA$ 能够与 $\tt AAA$ 产生 $1$ 种匹配方式； - 第一个选 $\tt AA$ 第二个选 $\tt A$，得到 $\tt AAA$ 能够与 $\tt AAA$ 产生 $1$ 种匹配方式； - 第一个选 $\tt AA$ 第二个选 $\tt AA$,得到 $\tt AAAA$ 能够与 $\tt AAA$ 产生 $0$ 种匹配方式。 所以一共 $4$ 种。 ### 数据范围及约定 - 对于 $30\%$ 的数据，$1\leq k\leq 25$，$1\le |s|\leq 10000$，$1\le a_i\leq 3$。 - 对于 $100\%$ 的数据，$1\leq k\leq100$，$1\le |s|\leq 10000$，$1\le a_i \leq10$。碱基序列的长度均不超过 $15$。字符集为大写字母。