Hide

Problem F
ilove Strings

It’s that time of year when love is in the air. You’re no stranger to love. You are obsessed with strings but not just any strings. You love “ilove” Strings. An “ilove” String is a string of length 5 with the following properties:

  • Alternates between vowels (excluding ‘y’ and ‘Y’) and consonants (including ‘y’ and ‘Y’)

  • Begins with a vowel (excluding ‘y’ and ‘Y’)

  • Consists of $5$ pairwise distinct characters (distinguishing between upper and lower case)

Examples of “ilove” Strings includes “ilove”, “image”, “IxoXO”, and “abide”. Examples of non-“ilove” Strings include , “ideas”, “maker”, “inane”, “oxOXo” and “abides”.

The loveliness of a string is the number of subsequences of the string that form an “ilove” String. Although “ilooove” is not an “ilove” String, it does have a loveliness of $3$.

Input

Input contains a single string of between $1$ and $100\, 000$ lowercase and uppercase Latin characters, representing the string whose loveliness is to be computed.

Output

For the provided string, print one line with a single integer $L$ — the loveliness of the string modulo $10^9+7$.

Sample Input 1 Sample Output 1
ilovestrings
4

Sample Input 2 Sample Output 2
idont
0

Sample Input 3 Sample Output 3
CAPital
1
CPU Time limit 2 seconds
Memory limit 1024 MB
Author
Travis Meade
Source 2021 ICPC North American Qualifier Contest (Jan 2022)
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in