[BalticOI 2005] Ancient Manuscript
题目描述
给定 Baltic 字符串的定义为:
- 全部为小写字母
- 最多只能有 $V_C$ 个连续的元音
- 最多只能有 $C_C$ 个连续的辅音
- 最多只能有 $V_E$ 个连续的元音相等
- 最多只能有 $C_E$ 个连续的辅音相等
`aeiou` 为元音,除了这五个字母之外的 21 个字母为辅音。
现在给定一个字符串,一些字符为小写字母一些字符为 `*`,您可以把 `*` 替换成任意一个小写字母。
求通过替换能使得这个字符串得到的不同的 Baltic 字符串的种类数。
输入输出格式
输入格式
第一行四个整数 $V_E,V_C,C_E,C_C$,具体含义见题面描述。
第二行一个字符串,具体含义见题目描述。
输出格式
一行一个整数代表通过替换能使得这个字符串得到的不同的 Baltic 字符串的种类数。
答案是 $64$ 位有符号整数。
输入输出样例
输入样例 #1
1 1 1 1
a**
输出样例 #1
105
输入样例 #2
1 1 1 1
b*i
输出样例 #2
0
输入样例 #3
1 2 1 2
ancient
输出样例 #3
1
输入样例 #4
4 4 4 4
man****ipt
输出样例 #4
261870
输入样例 #5
2 2 2 2
*boi*
输出样例 #5
546
说明
#### 数据规模与约定
对于 $100\%$ 的数据,$1 \le V_E \le V_C \le 4$,$1 \le C_E \le C_C \le 4$,$1 \le\ $字符串的长度$\ \le 15$。
#### 说明
翻译自 [BalticOI 2005 Day2 A Ancient Manuscript](https://boi.cses.fi/files/boi2005_day2.pdf)。