roy-and-birthday

Its Roy's birthday and he is decorating his house with balloons.
He has 26 different types of balloons. They are represented by [a-z].  

Now Roy does not want to have few particular balloons together. Actually he doesn't want to keep any of the two vowel (i.e [a,e,i,o,u] ) balloons together.
So, in one arrangement no two vowels should be together. Given the string of balloons there can be many such arrangements possible.
Help Roy in finding the number of possible arrangements.  

Number of such arrangements can be quite large, so print it modulo 1000000007 (10^9 + 7)  
Also, there's a chance that no such arrangement is possible. Print "-1" in such cases (without quotes)  

Input: 
First line contains T, number of test cases.
Each of next T lines contains a string composed of lower case letters representing all the balloons.  

Output:
For each test case print the required answer.

Constraints:
1 ≤ T ≤ 100
1 ≤ Length of string ≤ 1000000   (10^6)

Note: Sum of string lengths over all the test cases in one file does not exceed 1000000 (10^6)

SAMPLE INPUT
2
abe
ae

SAMPLE OUTPUT
2
-1

Explanation

Test #1: Possible arrangements are
[1] abe
[2] eba

Test #2: There are no any arrangements possible such that any two vowels are not together. So print -1.

Source: hackerearth | Difficulty: EASY
Tags: Combinatorics

Implementation

Mathematics


Solutions:
MOD = 1000000007
f = [1]
def fact():
	for i in range(1,1000011):
		f.append((f[i-1]*i)%MOD)
def fast_power(a,n):
	result = 1
	value = a
	power = n
	while power > 0:
		if power % 2 == 1:
			result = result * value
			result %= MOD
		value = value * value
		value %= MOD
		power = power/2
	return result
def inv(x):
	return fast_power(x,MOD-2)
def roy_and_bday_party():
	fact()
	for t in range(eval(input())):
		goku = input()
		glen = len(goku)
		freq = [0]*30
		v_count = 0 # stores number of vowels
		c_count = 0 # stores number of consonants
		for i in range(glen):
			freq[ord(goku[i]) - ord('a')] += 1
			if goku[i] == 'a' or goku[i] == 'e' or goku[i] == 'i' or goku[i] == 'o' or goku[i] == 'u':
				v_count += 1
			else:
				c_count += 1
		possible = c_count + 1 - v_count
		if possible < 0: # 
			print('-1')
		else:
			# formula for consonants is simply the number of permutations possible which can be found by n!
			c_res = f[c_count]
			# for vowels, say we had n consonants, then we can choose from (n+1) different places, giving (n+1)Cr * r!
			# i.e. (n+1)Cr means selecting r places from (n+1) places and then r! for permuations among r places
			# we simplify the formula a little by [ (n+1)! / r! * (n+1-r)! ] * r!
			# r! in numerator kills r! in dinominator and all we are left with is (n+1)! / (n+1-r)!
			v_res = f[c_count+1]*inv(f[possible])
			v_res %= MOD
			for i in range(26):
				tmp = chr(i+97)
				if tmp == 'a' or tmp == 'e' or tmp == 'i' or tmp == 'o' or tmp == 'u':
					v_res = v_res*inv(f[freq[i]])
					v_res %= MOD
				else:
					c_res = c_res*inv(f[freq[i]])
					c_res %= MOD
			print((v_res*c_res)%MOD)
roy_and_bday_party()