Problem Description

A Baltic string is defined as follows:

• It consists entirely of lowercase letters.
• It can have at most $V_C$ consecutive vowels.
• It can have at most $C_C$ consecutive consonants.
• It can have at most $V_E$ consecutive equal vowels.
• It can have at most $C_E$ consecutive equal consonants.

The vowels are aeiou, and the 21 other letters are consonants.

Given a string where some characters are lowercase letters and some are *, you can replace * with any lowercase letter.

Determine the number of distinct Baltic strings that can be obtained through replacement.

Input Format

The first line contains four integers $V_E, V_C, C_E, C_C$, which represent the constraints as described in the problem statement.
The second line contains a string, as described in the problem statement.

Output Format

Output a single integer representing the number of distinct Baltic strings that can be obtained through replacement.

The answer should be a 64-bit signed integer.

Sample Input and Output

Sample Input #1

1 1 1 1
a**

Sample Output #1

105

Sample Input #2

1 1 1 1
b*i

Sample Output #2

0

Sample Input #3

1 2 1 2
ancient

Sample Output #3

1

Sample Input #4

4 4 4 4
man****ipt

Sample Output #4

261870

Sample Input #5

2 2 2 2
*boi*

Sample Output #5

546

Notes

Data Size and Constraints

For $100\%$ of the data, $1 \le V_E \le V_C \le 4$, $1 \le C_E \le C_C \le 4$, and the length of the string is at most $15$.

Note

Translated from BalticOI 2005 Day2 A Ancient Manuscript.

见题面 Input 部分

见题面 Output 部分