[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 1
a**

样例输出 #1

105

样例 #2

样例输入 #2

1 1 1 1
b*i

样例输出 #2

0

样例 #3

样例输入 #3

1 2 1 2
ancient

样例输出 #3

1

样例 #4

样例输入 #4

4 4 4 4
man****ipt

样例输出 #4

261870

样例 #5

样例输入 #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。