## Baltic OI '05 P4 - Ancient Manuscript

View as PDF

Points: 12
Time limit: 2.0s
Memory limit: 512M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Baltic archaeologists are currently engaged in a very important project and have recently found an ancient manuscript that seems to be crucial for the understanding of the culture that inhabited the area they are exploring. The manuscript is full of drawings, so scientists are able to get a general feel for the subject of the document.

However, there is also a written part, and with that scientists are in trouble. Apart from the language used in the writing being a very ancient, several parts of manuscript were destroyed, some letters disappeared, and they are unable to completely understand what is written there.

One of the scientists said, that the words in the manuscript remind him of a language about which it is known that in any word there may be no more than and consecutive vowels and consonants, respectively, and that no more than and consecutive vowels and consonants, respectively, may be equal. That scientist left the group in search of a more precise information. The others, while waiting for that scientist to return, decided to check whether nothing in the manuscript contradicts his hypothesis and estimate the amount of work that may lie ahead, so they want to know in how many different ways the manuscript can possibly be deciphered. We must help them!

Note: vowels are aeiou and there are 21 other letters in the alphabet - consonants.

#### Input Specification

The first line of the input file contains four integers , , and () separated by single spaces. The second line contains one word extracted from the manuscript consisting of up to 15 Latin alphabet lowercase letters with missing characters (if any) designated by *.

#### Output Specification

One integer, describing in how many ways it is possible to make up a legal word based only on the constraints given. You may assume that the answer will fit into a 64-bit signed integer. It may happen that scientist's conjecture about the language is incorrect and that there are no ways to make up a legal word; in this case, the answer is, obviously, 0.

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