Sherlock And The Good Subsequences
Tag(s):

## Combinatorics, Medium

Problem
Editorial
Analytics

Sherlock found a string while he was searching for clues in a house. He knew that the string was not useful for the case, however the subsequences of the string were of great importance. He also knew that Mrs. Hudson didn't like bad subsequences and so Sherlock can only take home the good subsequences. He wants to know the number of subsequences he can take home and so he has asked for your help. He knows that the number of such subsequences can be large, so he wants the answer modulo 10^9 + 7.

Bad subsequences are those subsequences that have 2k + 1 characters (exactly k consonants followed by exactly one vowel which is again followed by exactly k consonants). Here, k is a positive integer.

We have considered 'a', 'e', 'i', 'o' and 'u' as vowels.

All the subsequences that are not bad can be considered good.

Note:- Sherlock doesn't take empty subsequences home.

Note:- Use of fast I/O is recommended.

See the sample case for better understanding.

Input format:

First line contains an integer T, denoting the number of test-cases.

Next T lines contains a string S of lowercase English alphabets.

Output format:

For each testcase, print the number of good subsequences modulo 10^9 + 7 in a new line.

Constraints:

1 <= T <= 10

1 <= |S| <= 500000

Subtask #1 (10 points) : 1 <= |S| <= 18

Subtask #2 (20 points) : 1 <= |S| <= 500

Subtask #3 (70 points) : Original Constraints

SAMPLE INPUT
2
car
royal
SAMPLE OUTPUT
6
27
Explanation

In first testcase, the possible 7 subsequences are listed below:-
"car" - is a bad subsequence as one consonant 'c' is followed by one vowel 'a' which is followed by one consonant 'r'.
"ca"  - good subsequence
"cr"  - good subsequence
"ar"  - good subsequence
"c"   - good subsequence
"a"   - good subsequence
"r"   - good subsequence
Hence, the number of good subsequences = 6.

Similarly, in second testcase, there are 27 good subsequences.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...