Problem Description

A Baltic string is defined as follows:

• It consists only of lowercase letters.
• It contains at most $V_C$ consecutive vowels.
• It contains at most $C_C$ consecutive consonants.
• It contains at most $V_E$ consecutive equal vowels.
• It contains at most $C_E$ consecutive equal consonants.

aeiou are vowels. The other 21 letters are consonants.

Now you are given a string in which some characters are lowercase letters and some characters are *. You may replace each * with any lowercase letter.

Find the number of different Baltic strings that can be obtained from this string by performing such replacements.

Input Format

The first line contains four integers $V_E,V_C,C_E,C_C$, whose meanings are given in the description.

The second line contains a string, whose meaning is given in the description.

Output Format

Output one integer: the number of different Baltic strings that can be obtained from the string after replacements.

It is guaranteed that the answer fits in a 64-bit signed integer.

1 1 1 1
a** 

105

1 1 1 1
b*i 

0

1 2 1 2
ancient 

1

4 4 4 4
man****ipt 

261870

2 2 2 2
*boi* 

546

Hint

Constraints

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

Notes

Translated from BalticOI 2005 Day2 A Ancient Manuscript。

Translated by ChatGPT 5