Chef considers a string consisting of lowercase English alphabets *beautiful* if all the characters of the string are vowels. 

Chef has a string S consisting of lowercase English alphabets, 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.

Note:
There are 26 characters in the English alphabet. Five of these characters are vowels: a, e, i, o, and u. The remaining 21 characters are consonants.
The closest vowel to a consonant is the vowel that is least distant from that consonant. For example, the distance between the characters d and e is 1 while the distance between the characters d and a is 3.
The distance between the characters z and a is 25 and not 1.

------ Input Format ------ 

- The first line of input will contain an integer T — the number of test cases. The description of T test cases follows.
- The first line of each test case contains an integer N, denoting the length of the string S.
- The second line of each test case contains a string S consisting of lowercase English alphabets.  

------ Output Format ------ 

For each test case, output the total number of distinct *beautiful* strings T that can be obtained by performing the given operations on the string S, modulo 10^{9} + 7. 

------ Constraints ------ 

$1 ≤ T ≤ 1000$
$1 ≤ N ≤ 10^{5}$
- Sum of $N$ over all test cases does not exceed $10^{5}$. 

----- Sample Input 1 ------ 
4
5
aeiou
5
abcde
8
starters
8
codechef

----- Sample Output 1 ------ 
1
2
4
4
----- explanation 1 ------ 
Test case $1$: All the characters of the string $S$ are vowels. Thus, none of the characters would be changed. The resulting string $T$ will be aeiou.  

Test case $2$:There are $2$ possible strings that can be obtained by performing the given operations on the string $S$. Those are aaaee and aaeee.

Source: codechef | Difficulty: EASY
Tags: String algorithms

Data structures

Mathematics


Solutions:
for _ in range(int(input())):
	n = int(input())
	s = input()
	c = 0
	for i in s:
		if i == 'c' or i == 'g' or i == 'l' or (i == 'r'):
			c += 1
	print(2 ** c % (10 ** 9 + 7))


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	res = 1
	mod = 1000000000 + 7
	for i in range(n):
		if s[i] == 'c' or s[i] == 'g' or s[i] == 'l' or (s[i] == 'r'):
			res = res * 2 % mod
	print(res)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	m = 'cglr'
	d = 0
	for j in s:
		if j in m:
			d += 1
	print(2 ** d % (10 ** 9 + 7))


for i in range(int(input())):
	a = ['c', 'g', 'l', 'r']
	n = int(input())
	s = input()
	k = 0
	for i in range(n):
		if s[i] in a:
			k += 1
	print(2 ** k % (10 ** 9 + 7))


for i in range(int(input())):
	n = int(input())
	s = input()
	vowel = ['a', 'e', 'i', 'o', 'u']
	d = ['c', 'g', 'l', 'r']
	v = 0
	c = 0
	for i in s:
		if i in vowel:
			v = v + 1
		if i in d:
			c = c + 1
	if v == n or c == 0:
		print(1)
	else:
		print(2 ** c % (10 ** 9 + 7))


t = int(input())
while t > 0:
	n = int(input())
	s = input()
	count = 0
	count_vow = 0
	for i in range(n):
		if s[i] == 'c' or s[i] == 'g' or s[i] == 'l' or (s[i] == 'r'):
			count = count + 1
		elif s[i] == 'a' or s[i] == 'e' or s[i] == 'i' or (s[i] == 'o') or (s[i] == 'u'):
			count_vow = count_vow + 1
	if count_vow == n:
		print(1)
	else:
		print(2 ** count % (10 ** 9 + 7))
	t = t - 1


for _ in range(int(input())):
	n = int(input())
	s = input()
	ans = 1
	m = 10 ** 9 + 7
	char = ['c', 'g', 'l', 'r']
	for i in s:
		if i in char:
			ans = ans * 2 % m
	print(ans % m)


for _ in range(int(input())):
	n = int(input())
	s = input()
	vowel = ['a', 'e', 'i', 'o', 'u']
	mid = ['c', 'g', 'l', 'r']
	(not_vowel, num_of_mid) = (0, 0)
	for i in s:
		if i not in vowel:
			not_vowel += 1
		if i in mid:
			num_of_mid += 1
	if not_vowel == 0 or num_of_mid == 0:
		print('1')
	else:
		print(2 ** num_of_mid % (10 ** 9 + 7))


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	alpha = 'abcdefghijklmnopqrstuvwxyz'
	(vowels, n_str) = ({'a', 'e', 'i', 'o', 'u'}, 1)
	for j in range(n):
		if s[j] not in vowels:
			(l, count) = ([], 0)
			for e in vowels:
				l.append(abs(alpha.index(s[j]) - alpha.index(e)))
			l.sort()
			for x in range(len(l)):
				if l[x] == l[0]:
					count += 1
			n_str *= count
	print(n_str % (10 ** 9 + 7))


for _ in range(int(input())):
	N = int(input())
	S = input()
	vowelSet = ['a', 'e', 'i', 'o', 'u']
	noOfT = 1
	for char in S:
		if char not in vowelSet:
			countV = 0
			A = [abs(ord(char) - ord(vowel)) for vowel in vowelSet]
			for vowel in vowelSet:
				if abs(ord(char) - ord(vowel)) == min(A):
					countV += 1
			noOfT *= countV
	print(noOfT % (10 ** 9 + 7))


for i in range(int(input())):
	n = int(input())
	x = input()
	count = 0
	for i in x:
		if i in ('c', 'g', 'l', 'r'):
			count = count + 1
	print(2 ** count % (10 ** 9 + 7))


x = int(input())
ip = []
for mc in range(0, x):
	l = int(input())
	f = str(input())
	ip.append(f)
for jj in ip:
	ie = []
	pmrt = [97, 101, 105, 111, 117]
	for hh in jj:
		yr = ord(hh)
		if yr in pmrt:
			ie.append(1)
		else:
			up = 0
			ue = 0
			if yr < 97:
				up = None
				ue = 97 - yr
			if yr > 97 and yr < 101:
				up = yr - 97
				ue = 101 - yr
			if yr > 101 and yr < 105:
				up = yr - 101
				ue = 105 - yr
			if yr > 105 and yr < 111:
				up = yr - 105
				ue = 111 - yr
			if yr > 111 and yr < 117:
				up = yr - 111
				ue = 117 - yr
			if yr > 117:
				up = yr - 117
				ue = None
			if up == ue:
				ie.append(2)
			else:
				ie.append(1)
	ans = 1
	for jjd in ie:
		ans *= jjd
	print(ans % (10 ** 9 + 7))


for _ in range(int(input())):
	_ = int(input())
	s = input()
	lst = ['c', 'g', 'l', 'r']
	c = 0
	for ele in s:
		if ele in lst:
			c += 1
	print(2 ** c % (10 ** 9 + 7))


tc = int(input())
for _ in range(tc):
	n = int(input())
	a = list(input())
	count = 0
	gorb = ['c', 'g', 'l', 'r']
	for i in a:
		if i in gorb:
			count += 1
	print(2 ** count % (10 ** 9 + 7))


T = int(input())
for i in range(T):
	N = int(input())
	S = input().lower()
	A = ord('a') - 96
	B = ord('e') - 96
	C = ord('i') - 96
	D = ord('o') - 96
	E = ord('u') - 96
	P1 = (A + B) // 2
	P2 = (C + B) // 2
	P3 = (C + D) // 2
	P4 = (D + E) // 2
	c = 0
	for j in S:
		if ord(j) - 96 == P1 or ord(j) - 96 == P2 or ord(j) - 96 == P3 or (ord(j) - 96 == P4):
			c += 1
	if c >= 1:
		print(2 ** c % (10 ** 9 + 7))
	else:
		print('1')


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	t = 1
	for i in s:
		if i == 'c' or i == 'g' or i == 'l' or (i == 'r'):
			t = t * 2
		else:
			t = t
	print(t % (10 ** 9 + 7))


for _ in range(int(input())):
	N = int(input())
	text = input()
	no_of_beautiful = 1
	MOD = 10 ** 9 + 7
	for char in text:
		if char in 'cglr':
			no_of_beautiful *= 2
			no_of_beautiful %= MOD
	print(no_of_beautiful)


T = int(input())
for i in range(T):
	n = int(input())
	s = input()
	answer = 1
	arr = ['c', 'g', 'l', 'r']
	for i in s:
		if i in arr:
			answer *= 2
	answer %= 10 ** 9 + 7
	print(answer)


test = int(input())
for i in range(test):
	n = int(input())
	str = input()
	a = ['c', 'g', 'l', 'r']
	ans = 1
	for ch in str:
		if ch in a:
			ans *= 2
	ans %= 10 ** 9 + 7
	print(ans)


n = int(input())
for i in range(n):
	l = int(input())
	ct = 1
	lst = ['a', 'e', 'i', 'o', 'u']
	se = ['c', 'g', 'l', 'r']
	st = input()
	for j in st:
		if j in se:
			ct = ct * 2 % 1000000007
	print(ct)


for tc in range(int(input())):
	n = int(input())
	s = input()
	a = {'c', 'g', 'l', 'r'}
	count = 0
	for ele in s:
		if ele in a:
			count += 1
	mod = pow(10, 9) + 7
	ans = pow(2, count) % mod
	print(ans)


for _ in range(int(input())):
	n = int(input())
	s = input()
	p = 'cglr'
	g = 0
	for x in p:
		g += s.count(x)
	print(2 ** g % (10 ** 9 + 7))


vowels = ['a', 'e', 'i', 'o', 'u']
for _ in range(int(input())):
	n = int(input())
	s = input()
	dist = 1
	for i in range(n):
		if s[i] not in vowels:
			if s[i] == 'c' or s[i] == 'g' or s[i] == 'l' or (s[i] == 'r'):
				dist *= 2
	print(dist % (10 ** 9 + 7))


for _ in range(int(input())):
	n = int(input())
	s = input()
	vo = 'cglr'
	i = 0
	for x in s:
		if x in vo:
			i = i + 1
	print(2 ** i % (10 ** 9 + 7))


mod = 10 ** 9 + 7
db = ['c', 'g', 'l', 'r']
for _ in range(int(input())):
	n = int(input())
	s = input()
	count = 0
	for i in db:
		count += s.count(i)
	print(2 ** count % mod)


for _ in range(int(input())):
	l = int(input())
	s = input()
	total = s.count('c') + s.count('g') + s.count('l') + s.count('r')
	answer = 2 ** total % (10 ** 9 + 7)
	print(answer)


from collections import defaultdict
MOD = 1000000007

def closest_vow():
	vo = 'aeiou'
	co = 'bcdfghjklmnpqrstvwxyz'
	d = defaultdict(list)
	for c in co:
		min_dist = float('inf')
		for v in vo:
			dist = abs(ord(v) - ord(c))
			if dist < min_dist:
				min_dist = dist
				d[c] = [v]
			elif dist == min_dist and len(d[c]) == 1:
				d[c].append(v)
	return {k: v for (k, v) in d.items() if len(v) == 2}

def beaut_str(s, cl):
	count = 0
	for c in s:
		if c in cl:
			count += 1
	return 2 ** count % MOD
for _ in range(int(input())):
	n = int(input())
	s = input()
	cl = closest_vow()
	print(beaut_str(s, cl))


def main():
	T = int(input())
	for _ in range(T):
		N = int(input())
		S = input()[:N]
		ans = 0
		for i in range(N):
			if S[i] == 'c' or S[i] == 'g' or S[i] == 'l' or (S[i] == 'r'):
				ans += 1
		print(2 ** ans % (10 ** 9 + 7))
main()


T = int(input())
for i in range(T):
	N = int(input())
	A = input()
	possible = 0
	for i in range(N):
		if A[i] == 'c' or A[i] == 'g' or A[i] == 'l' or (A[i] == 'r'):
			possible += 1
	print(2 ** possible % (10 ** 9 + 7))


def getNumber(char):
	li = [ord('a'), ord('e'), ord('i'), ord('o'), ord('u')]
	num = ord(char)
	min = float('inf')
	ans = 1
	for ele in li:
		if num > ele:
			dis = num - ele
		else:
			dis = ele - num
		if dis == 0:
			break
		elif dis < min:
			count = 1
			min = dis
		elif dis == min:
			count += 1
	if min == float('inf'):
		return 1
	else:
		return count
t = int(input())
for z in range(t):
	n = int(input())
	string = input()
	ans = 1
	for char in string:
		ans *= getNumber(char)
	m = 1000000007
	print(ans % m)


from collections import Counter
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	ans = 1
	for i in s:
		if i in 'aeiou':
			continue
		else:
			if i > 'a' and i < 'e':
				if ord(i) - ord('a') == ord('e') - ord(i):
					ans = ans * 2 % 1000000007
			if i > 'e' and i < 'i':
				if ord(i) - ord('e') == ord('i') - ord(i):
					ans = ans * 2 % 1000000007
			if i > 'i' and i < 'o':
				if ord(i) - ord('i') == ord('o') - ord(i):
					ans = ans * 2 % 1000000007
			if i > 'o' and i < 'u':
				if ord(i) - ord('o') == ord('u') - ord(i):
					ans = ans * 2 % 1000000007
	print(ans)


from collections import Counter
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	ans = 1
	for i in s:
		if i in 'cglr':
			ans = ans * 2 % 1000000007
	print(ans)


T = int(input())
VOWELS = ['a', 'e', 'i', 'o', 'u']
MODULO = 1000000007
for t in range(T):
	n = int(input())
	s = input()
	total = 1
	for c in s:
		if c not in VOWELS:
			best = 27
			p = 1
			for v in VOWELS:
				dist = abs(ord(c) - ord(v))
				if dist < best:
					best = dist
					p = 1
				elif dist == best:
					p = 2
			total = total * p % MODULO
	print(total)


import string
letters = string.ascii_lowercase
vowels = 'aeiou'
t = int(input())
ans = [1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1]
for i in range(t):
	n = int(input())
	s = str(input())
	count = 1
	for j in s:
		if j not in vowels:
			count *= ans[letters.index(j)]
	print(count % 1000000007)


import os, sys, io, math
from re import *
from math import *
from array import *
from heapq import *
from bisect import *
from functools import *
from itertools import *
from statistics import *
from collections import *
I = lambda : [*map(int, sys.stdin.readline().split())]
IP = lambda : map(int, input().split())
IS = lambda : input()
IN = lambda : int(input())
IF = lambda : float(input())

def f():
	(n, s, res) = (IN(), IS(), 1)
	for i in s:
		if i == 'c' or i == 'g' or i == 'l' or (i == 'r'):
			res = res * 2 % 1000000007
	return res
for _ in range(IN()):
	print(f())


for i in range(int(input())):
	inp = int(input())
	lst = list(input())
	ans = [1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1]
	arr = []
	for i in lst:
		arr.append(ans[ord(i) - 97])
	answer = 2 ** arr.count(2) % 1000000007
	print(answer)


for _ in range(int(input())):
	l = int(input())
	s = input()
	tot = s.count('c') + s.count('g') + s.count('l') + s.count('r')
	ans = 2 ** tot % (10 ** 9 + 7)
	print(ans)


n = int(input())
for i in range(n):
	a = int(input())
	b = input().lower()
	c = [99, 103, 108, 114]
	d = 1
	for i in list(b):
		if ord(i) in c:
			d *= 2
	print(d % (pow(10, 9) + 7))


t = int(input())
for i in range(t):
	n = int(input())
	s = input().lower()
	xx = [99, 103, 108, 114]
	p = 1
	for i in list(s):
		if ord(i) in xx:
			p *= 2
	print(p % (pow(10, 9) + 7))


import sys, math, bisect
from collections import defaultdict
inp = sys.stdin.readline
for _ in range(int(inp())):
	mod = 10 ** 9 + 7
	n = int(inp())
	s = inp().strip()
	arr = [ord('a') - ord('a'), ord('e') - ord('a'), ord('i') - ord('a'), ord('o') - ord('a'), ord('u') - ord('a')]
	arr_set = set(arr)
	ans = 1
	for c in s:
		num = ord(c) - ord('a')
		if num in arr_set:
			continue
		idx = bisect.bisect_left(arr, num)
		if idx == 0 or idx == 5:
			continue
		if abs(arr[idx] - num) == abs(arr[idx - 1] - num):
			ans *= 2
			ans %= mod
			continue
	print(ans)


for _ in range(int(input())):
	N = int(input())
	S = input().lower()
	xx = [99, 103, 108, 114]
	p = 1
	for i in list(S):
		if ord(i) in xx:
			p *= 2
	print(p % (pow(10, 9) + 7))


for _ in range(int(input())):
	a = int(input())
	s = input()
	va = s.count('c') + s.count('g') + s.count('l') + s.count('r')
	print(2 ** va % (10 ** 9 + 7))


testcases = int(input())
for i in range(testcases):
	n = int(input())
	data = str(input())
	val = data.count('c') + data.count('g') + data.count('l') + data.count('r')
	ans = 2 ** val % (10 ** 9 + 7)
	print(ans)


for i in range(int(input())):
	n = int(input())
	sr = input()
	mod = 10 ** 9 + 7
	count = 1
	for i in sr:
		if i == 'c' or i == 'g' or i == 'l' or (i == 'r'):
			count *= 2
			count %= mod
	print(count)


t = int(input())
x = []
(a, e, i, o, u) = (ord('a'), ord('e'), ord('i'), ord('o'), ord('u'))
for ni in range(t):
	n = int(input())
	s = input()
	l = list()
	c = 1
	mod = 10 ** 9 + 7
	for j in s:
		l1 = [abs(ord(j) - a), abs(ord(j) - e), abs(ord(j) - i), abs(ord(j) - o), abs(ord(j) - u)]
		x = l1.count(min(l1))
		c = c * x
		c %= mod
	print(c)


for _ in range(int(input())):
	n = int(input())
	s = input()
	c = 1
	f = 0
	for i in s:
		if i == 'a' or i == 'e' or i == 'i' or (i == 'o') or (i == 'u'):
			continue
		else:
			f = 1
			if i == 'c' or i == 'g' or i == 'l' or (i == 'r'):
				c = c * 2
	if f == 0:
		print(1)
	else:
		print(c % 1000000007)


T = int(input())
while T:
	N = int(input())
	S = input()
	ls = ['c', 'g', 'l', 'r']
	pos = 1
	for s in S:
		if s in ls:
			pos = pos * 2
	print(pos % 1000000007)
	T = T - 1


t = int(input())
while t:
	n = int(input())
	l = list(input())
	s = 1
	for i in l:
		if i in ('c', 'g', 'l', 'r'):
			s *= 2
	else:
		print(s % (10 ** 9 + 7))
	t -= 1


for _ in range(int(input())):
	n = int(input())
	s = input()
	p = 1
	k = 0
	for i in s:
		if i not in ('a', 'e', 'i', 'o', 'u'):
			if i in ('c', 'g', 'l', 'r'):
				p = p * 2
	print(p % (10 ** 9 + 7))


for _ in range(int(input())):
	N = int(input())
	s = input()
	equi = ['c', 'g', 'l', 'r']
	ans = 0
	for i in s:
		if i in equi:
			ans += 1
	print(2 ** ans % 1000000007)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	v = ['c', 'g', 'l', 'r']
	count = 1
	for i in s:
		if i in v:
			count *= 2
	print(count % (10 ** 9 + 7))


vpos = [ord('a'), ord('e'), ord('i'), ord('o'), ord('u')]
for _ in range(int(input())):
	n = int(input())
	s = input()
	options = 1
	for c in s:
		if not c in 'aeiou':
			d = [abs(ord(c) - v) for v in vpos]
			d.sort()
			if d[0] == d[1]:
				options *= 2
	print(options % (10 ** 9 + 7))