[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)。