Chef considers a string consisting of lowercase English alphabet beautiful if all the characters of the string are vowels.
Chef has a string S consisting of lowercase English alphabet, of length N. He wants to convert S into a beautiful string T. In order to do so, Chef does the following operation on every character of the string:
- If the character is a consonant, change the character to its closest vowel.
- If the character is a vowel, don’t change it.
Chef realizes that the final string T is not unique. Chef wonders, what is the total number of distinct beautiful strings T that can be obtained by performing the given operations on the string S.
Since the answer can be huge, print it modulo 10^9 + 7.
- There are 26 characters in the English alphabet. Five of these characters are vowels:
u. The remaining 21 characters are consonants.
- The closest vowel to a consonant is the vowel that is at least distant from that consonant. For example, the distance between the characters
eis 1 while the distance between the characters
- The distance between the characters
ais 25 and not 1.
In this problem we need to change all the consonants to their nearest vowel. The consonants that have a unique vowel nearest to it will just have one choice, that is to change into that vowel, however for vowels that have 2 vowels at same closest distance, it will have 2 choices. Thus we just need to calculate all consonants that have 2 choices. Let us denote this by count. Then our final answer would be:
O(N), for each test case.