Problem J
Speaking of Which
Your friend Edvin was going to tell you his password to his favourite website, so that you could check out how awesome it is. Edvin is sure that nobody but him and you speak the Robber Language, so he encrypted it using this simple technique, and wrote it down on a note. After trying the password and realising it does not work, you found out that Edvin was drunk during the transformation. Now you want to find out in how many ways the password might have looked originally.
You are given an encrypted password which Edvin has attempted to translate into the Robber Language. Your task is to determine how many passwords might produce the encrypted password. You may assume that the only thing Edvin did wrong, was when scanning through the word with his eyes, he sometimes missed to transform some consonants using the rule above. Edvin is not deterministic in his failures, i.e. if he missed to transform a consonant once, it is not necessary that he would miss it if it occured again later in the string.
A vowel is considered to be one of the letters "a", "e", "i", "o" and "u". A consonant is any other letter.
Input
Input consists of one encrypted password, the resulting word from Edvins translation. The word can be as long as $1\, 000\, 000$ characters. It will solely consist of lower case letters a-z.
Output
Output should consist of one number, the number of ways the password might have looked before Edvin translated it. Since this number may be huge, print the remainder modulo $1\, 000\, 009$.
| Sample Input 1 | Sample Output 1 |
|---|---|
car |
1 |
| Sample Input 2 | Sample Output 2 |
|---|---|
cocar |
2 |
| Sample Input 3 | Sample Output 3 |
|---|---|
cocaror |
4 |
