Ancient Manuscript

Time limit1sMemory limit128 MB

Summary

Count ways to fill '*' letters in a word so runs of vowels/consonants respect maximum length and maximum equal-letter-repeat limits, using DP over letter classes and previous letter identity.

Level: Medium5 of 10
Topics: Dynamic programming, String, Implementation
Solved: No attempts yet

Problem

Baltic archaeologists are working on an important project and have recently found an ancient manuscript that seems crucial for understanding the culture that once inhabited the region they are exploring. The manuscript is full of drawings, so the scientists can get a general sense of the document's subject.

However, there is also a written part, and that is where the trouble begins. Besides the language being very ancient, several parts of the manuscript were destroyed: some letters have disappeared, and the text cannot be read in full.

One scientist remarked that the words remind him of a language with the following known rules. In any word there may be at most $VC$ consecutive vowels and at most $CC$ consecutive consonants, and at most $VE$ consecutive vowels and at most $CE$ consecutive consonants may be equal (that is, the same letter repeated).

That scientist left to look for more precise information. While waiting, the others want to check whether anything in the manuscript contradicts the hypothesis and to estimate the work ahead, so they want to know in how many different ways the manuscript could be deciphered. Help them!

Note: the vowels are aeiou; the remaining 21 letters of the alphabet are consonants.

Input

The first line contains four integers $VE$ , $VC$ , $CE$ , and $CC$ ( $1 \le VE \le VC \le 4$ , $1 \le CE \le CC \le 4$ ), separated by single spaces. The second line contains one word taken from the manuscript, consisting of up to 15 lowercase Latin letters, where each missing character is written as *.

Output

Print one integer: the number of ways to form a legal word given only the constraints above. The answer fits into a signed 64-bit integer. It may happen that the scientist’s conjecture is wrong and no legal word can be formed; in that case the answer is 0.

Examples5

Example 1
Input
```
1 1 1 1
a**
```
Expected output
```
105
```
Example 2
Input
```
1 1 1 1
b*i
```
Expected output
```
0
```
Example 3
Input
```
1 2 1 2
ancient
```
Expected output
```
1
```
Example 4
Input
```
4 4 4 4
man****ipt
```
Expected output
```
261870
```
Example 5
Input
```
2 2 2 2
*boi*
```
Expected output
```
546
```