P6710 [BalticOI 2005] Ancient Manuscript (Day2)

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.

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 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.

#### 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](https://boi.cses.fi/files/boi2005_day2.pdf)。 Translated by ChatGPT 5