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