Pleasant Word

Time limit1sMemory limit128 MB

Summary

Count ways to fill blanks in a word with uppercase letters so it avoids three consecutive vowels or consonants and contains at least one 'L'.

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

Problem

Some letters in an uppercase word have been erased and replaced with underscores (_). Replace each underscore with one uppercase English letter.

The vowels are A, E, I, O, and U; every other letter is a consonant. A pleasant word must satisfy all of these conditions:

It does not contain three consecutive vowels.
It does not contain three consecutive consonants.
It contains the letter L at least once.

Given the partially erased word, count how many replacements produce a pleasant word.

Input

The first line contains the partially erased word. Its length is at most 100, and it contains only uppercase English letters and underscores (_). The number of underscores is at most 10.

Output

Print the number of ways to replace the underscores with letters so that the resulting word is pleasant.

Hint

The answer does not exceed 2^63 - 1.

Examples3

Example 1
Input
```
L_V
```
Expected output
```
5
```
Example 2
Input
```
V__K
```
Expected output
```
10
```
Example 3
Input
```
JA_BU_K_A
```
Expected output
```
485
```