Ancient Manuscript#3016
Baltic archaeologists are currently engaged in a very important project and have recently discovered an ancient manuscript that seems to be crucial for understanding the culture that inhabited the area they are exploring. The manuscript is full of drawings, so scientists are able to get a general idea of the document's subject.
However, there is also a written part that is problematic for the researchers. The language used is very ancient, and several parts of the manuscript have been destroyed, so some letters are missing and the scientists cannot completely understand what is written.
One of the scientists mentioned that the words in the manuscript reminded him of a language in which it is known that no more than V_C consecutive vowels or C_C consecutive consonants can appear in any word, and no more than V_E of the same vowel or C_E of the same consonant can appear consecutively.
That scientist left in search of more precise information. The others, while waiting for that scientist to return, decided to check whether anything in the manuscript contradicts his hypothesis and to estimate the amount of work that may be ahead. They want to know in how many different ways the manuscript could possibly be deciphered. We must help them!
Note: vowels are "aeiou", and there are other letters in the alphabet – consonants.
The first line contains four integers V_E, V_C, C_E and C_C (1 \le V_E \le V_C \le 4, 1 \le C_E \le C_C \le 4) separated by spaces. The second line contains one word extracted from the manuscript, consisting of up to lowercase Latin letters, with missing characters (if any) denoted by "*".
Output one integer, the number of ways it is possible to construct a legal word using only the given constraints. You may assume the answer fits into a -bit signed integer. It is possible that the scientist's hypothesis is incorrect and there are no valid ways to form a word; in this case, the answer is .
Example 1