Souvik and Permutations
Tag(s):

## Easy

Problem
Editorial
Analytics

Souvik loves to code. He is very good at solving algorithmic challenges. He also loves to play Counter Strike. But he doesn't play Counter Strike as well as he thinks.

Even after a lot of practice playing CS, he is not able to defeat his friend Tirth. Now, Souvik wants to take revenge by beating Tirth in coding challenges. So, he challenges Tirth to find the number of different permutations of string s such that all vowels come before all the consonants.

Since the answer can be very large, you need to print answer modulo 10^9+7.

### Input

First line contains a single integer t denoting the number of test cases.

Each of the next t lines contains a string s consisting only lowercase letters.

### Ouput

For each testcase, print a single line containing required output.

### Constraints

1 <= t <= 20
1 <= length(s) <= 10^5

30% score :
1 <= length(s) <= 18

100% score :
Original constraints

SAMPLE INPUT
4
en
mn
paq
adiiaapp
SAMPLE OUTPUT
1
2
2
30
Explanation

Test case 2 :
2 possible permutations - 'mn', 'nm'
Test case 3 :
2 possible permutations - 'apq', 'aqp'

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: 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, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

CodeBattle

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > Searching