Sereja has a string A consisting of n lower case English letters. 

Sereja calls two strings X and Y each of length n similar if they can be made equal by applying the following operation at most once in each of them.

- Chose any two position i, j in the string (i can be equal to j too). Swap the characters at position i with character at position j.

For example strings "abcd" and "acbd" are similar, strings "ab" and "ab" are similar, but strings "abcde" and "bcdea" are not similar. Note that strings  "abc" and "cab" are also similar, as you can swap 'a' and 'c' in the first string to get "cba" and 'a' and 'b' in the second string to get "cba". 

Now Sereja is interested in finding number of ordered pairs of non similar strings X and Y such that they can be constructed from a given string A by permutation of its characters. As answer could be large, please output your answer modulo  (109 + 7).

Note 

A string s (of size n) is said to be constructed from string t (also of size n) by permutation of its characters if there exists a permutation P (of length n), such that s[i] = t[P[i]] for each i from 1 to n.

-----Input-----
- First line contain integer T - number of test cases. 
- For each of the next T lines: 
	
- Each line contains a string A as defined in the problem.

-----Output-----
For each test case, output answer modulo 1000000007 (109 + 7) in separate line. 

-----Constraints-----
- 1 ≤ T ≤  10 
- 1 ≤ n ≤  10^5 

-----Constraints-----
- Subtask #1: 1 ≤ n ≤  10  (25 points)
- Subtask #2: 1 ≤ n ≤  100  (25 points)
- Subtask #3: 1 ≤ n ≤  1000  (25 points)
- Subtask #4: original constraints (25 points)

-----Example-----
Input:
2
z
abcd

Output:
0
144

Difficulty: interview

Starter code:

Solutions:
import math
def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modin(a, m):
    g, x, y = egcd(a, m)
    return x % m
# def gcdexten(a,b,x,y):
# 	if a == 0:
# 		x = 0
# 		y = 1
# 		return b
# 	x1 = y1 = 0
# 	gcd = gcdexten(b%a,a,x1,y1)

# 	x = y1 - (b/a) * x1
# 	y = x1
# 	return gcd

# def modin(a):
# 	m = 10**9 + 7
# 	x = y = 0
# 	g = gcdexten(a,m,x,y)
# 	res = (x%m + m)%m
# 	return res

# void modInverse(int a, int m)
# {
#     int x, y;
#     int g = gcdExtended(a, m, &x, &y);
#     if (g != 1)
#         cout << "Inverse doesn't exist";
#     else
#     {
#         // m is added to handle negative x
#         int res = (x%m + m) % m;
#         cout << "Modular multiplicative inverse is " << res;
#     }
# }
# int gcdExtended(int a, int b, int *x, int *y)
# {
#     // Base Case
#     if (a == 0)
#     {
#         *x = 0, *y = 1;
#         return b;
#     }
 
#     int x1, y1; // To store results of recursive call
#     int gcd = gcdExtended(b%a, a, &x1, &y1);
 
#     // Update x and y using results of recursive
#     // call
#     *x = y1 - (b/a) * x1;
#     *y = x1;
 
#     return gcd;
# }
def combi(a,b):
	mod = 10**9 + 7
	if a < b:
		return 0
	if a == 1:
		return 1
	if b < a/2:
		b = a - b
	temp = 1
	for i in range(b + 1,a + 1):
		temp = (temp * i%mod)%mod
	denom = modin(math.factorial(a-b),mod)
	# print denom
	return (temp%mod * denom%mod)%mod
for _ in range(eval(input())):
	mod = 10**9 + 7
	string1 = input()
	n = len(string1)
	dict1 = {}
	count = 0
	alpha = set()
	for ele in string1:
		if ele in dict1:
			dict1[ele] += 1
		else:
			dict1[ele] = 1
			alpha.add(ele)
			count += 1
 
	count_list = []
	total = 1
	rem = n
	for ele in alpha:
		total = (total % mod) * (combi(rem,dict1[ele]) % mod)%mod
		rem -= dict1[ele]
		count_list.append(dict1[ele])
 
	sum_list = [n - count_list[0]]
	for i in range(1,count):
		sum_list.append(sum_list[i - 1] - count_list[i])
 
	sub_2 = 0
	sub = 0
	for i in count_list:
		sub_2 += (n - i) * i
	sub_2 /= 2
	# print sub_2
 
	sub_3 = 0
	for i in range(count):
		for j in range(i + 1,count):
			sub_3 += count_list[i] * count_list[j] * sum_list[j]
 
	sub_3 = 2 * sub_3
 
	sub_4_4 = 0
	for i in range(count):
		for j in range(i + 1,count):
			for k in range(j + 1,count):
				sub_4_4 += count_list[i] * count_list[j] * count_list[k] * sum_list[k]
 
	sub_4_4 *= 3
	sub_4_2 = 0
	for i in range(count):
		for j in range(i + 1,count):
			sub_4_2 += (count_list[i] * (count_list[i] - 1) * count_list[j] * (count_list[j] - 1))/4
 
	sub_4_3 = 0
	for i in range(count):
		temp = 0
		for j in range(count):
			if j != i:
				temp += count_list[j] * (n - count_list[i] - count_list[j])
		temp /= 2
		sub_4_3 += ((count_list[i] * (count_list[i] - 1)) * temp)/2
		# print sub_4_3
	sub_4_3 *= 2
	# sub_4 = ((sub_4_2%mod + sub_4_3%mod) + sub_4_4%mod)%mod
	# sub_tot = ((sub_2%mod + sub_3%mod)%mod + sub_4%mod)%mod
	sub_4 = sub_4_3 + sub_4_4 + sub_4_2
	sub_tot = sub_2 + sub_3 + sub_4

	# print((total * (total - 1)) - (total * sub_tot%mod))%mod
	# print ((total)* (total - 1 - (((sub_3 + sub_2)%mod + (sub_4_4 +sub_4_3)%mod)%mod + sub_4_2%mod)))% mod 
	print((total * (total - (sub_tot + 1)%mod)%mod)%mod)

import math
def combi(a,b):
	mod = 10**9 + 7
	if a < b:
		return 0
	if a == 1:
		return 1
	if b < a/2:
		b = a - b
	temp = 1
	for i in range(b + 1,a + 1):
		temp = (temp * i%mod)%mod
	temp /= math.factorial(a - b)
	return temp
for _ in range(eval(input())):
	mod = 10**9 + 7
	string1 = input()
	n = len(string1)
	dict1 = {}
	count = 0
	alpha = set()
	for ele in string1:
		if ele in dict1:
			dict1[ele] += 1
		else:
			dict1[ele] = 1
			alpha.add(ele)
			count += 1
 
	count_list = []
	total = 1
	rem = n
	for ele in alpha:
		total = (total % mod) * (combi(rem,dict1[ele]) % mod)%mod
		rem -= dict1[ele]
		count_list.append(dict1[ele])
 
	sum_list = [n - count_list[0]]
	for i in range(1,count):
		sum_list.append(sum_list[i - 1] - count_list[i])
 
	sub_2 = 0
	sub = 0
	for i in count_list:
		sub_2 += (n - i) * i
	sub_2 /= 2
	# print sub_2
 
	sub_3 = 0
	for i in range(count):
		for j in range(i + 1,count):
			sub_3 += count_list[i] * count_list[j] * sum_list[j]
 
	sub_3 = 2 * sub_3
 
	sub_4_4 = 0
	for i in range(count):
		for j in range(i + 1,count):
			for k in range(j + 1,count):
				sub_4_4 += count_list[i] * count_list[j] * count_list[k] * sum_list[k]
 
	sub_4_4 *= 3
	sub_4_2 = 0
	for i in range(count):
		for j in range(i + 1,count):
			sub_4_2 += (count_list[i] * (count_list[i] - 1) * count_list[j] * (count_list[j] - 1))/4
 
	sub_4_3 = 0
	for i in range(count):
		temp = 0
		for j in range(count):
			if j != i:
				temp += count_list[j] * (n - count_list[i] - count_list[j])
		temp /= 2
		sub_4_3 += ((count_list[i] * (count_list[i] - 1)) * temp)/2
		# print sub_4_3
	sub_4_3 *= 2
	# sub_4 = ((sub_4_2%mod + sub_4_3%mod) + sub_4_4%mod)%mod
	# sub_tot = ((sub_2%mod + sub_3%mod)%mod + sub_4%mod)%mod
	sub_4 = sub_4_3 + sub_4_4 + sub_4_2
	sub_tot = sub_2 + sub_3 + sub_4

	# print((total * (total - 1)) - (total * sub_tot%mod))%mod
	# print ((total)* (total - 1 - (((sub_3 + sub_2)%mod + (sub_4_4 +sub_4_3)%mod)%mod + sub_4_2%mod)))% mod 
	print((total * (total - (sub_tot + 1)%mod)%mod)%mod)

import math
def combi(a,b):
	mod = 10**9 + 7
	if a < b:
		return 0
	if a == 1:
		return 1
	if b < a/2:
		b = a - b
	temp = 1
	for i in range(b + 1,a + 1):
		temp = (temp * i%mod)%mod
	temp /= math.factorial(a - b)
	return temp
for _ in range(eval(input())):
	mod = 10**9 + 7
	string1 = input()
	n = len(string1)
	dict1 = {}
	count = 0
	alpha = set()
	for ele in string1:
		if ele in dict1:
			dict1[ele] += 1
		else:
			dict1[ele] = 1
			alpha.add(ele)
			count += 1
 
	count_list = []
	total = 1
	rem = n
	for ele in alpha:
		total = (total % mod) * (combi(rem,dict1[ele]) % mod)%mod
		rem -= dict1[ele]
		count_list.append(dict1[ele])
 
	sum_list = [n - count_list[0]]
	for i in range(1,count):
		sum_list.append(sum_list[i - 1] - count_list[i])
 
	sub_2 = 0
	sub = 0
	for i in count_list:
		sub_2 += (n - i) * i
	sub_2 /= 2
	# print sub_2
 
	sub_3 = 0
	for i in range(count):
		for j in range(i + 1,count):
			sub_3 += count_list[i] * count_list[j] * sum_list[j]
 
	sub_3 = 2 * sub_3
 
	sub_4_4 = 0
	for i in range(count):
		for j in range(i + 1,count):
			for k in range(j + 1,count):
				sub_4_4 += count_list[i] * count_list[j] * count_list[k] * sum_list[k]
 
	sub_4_4 *= 3
	sub_4_2 = 0
	for i in range(count):
		for j in range(i + 1,count):
			sub_4_2 += (count_list[i] * (count_list[i] - 1) * count_list[j] * (count_list[j] - 1))/4
 
	sub_4_3 = 0
	for i in range(count):
		temp = 0
		for j in range(count):
			if j != i:
				temp += count_list[j] * (n - count_list[i] - count_list[j])
		temp /= 2
		sub_4_3 += ((count_list[i] * (count_list[i] - 1)) * temp)/2
		# print sub_4_3
	sub_4_3 *= 2
	# sub_4 = ((sub_4_2%mod + sub_4_3%mod) + sub_4_4%mod)%mod
	# sub_tot = ((sub_2%mod + sub_3%mod)%mod + sub_4%mod)%mod
	sub_4 = sub_4_3 + sub_4_4 + sub_4_2
	sub_tot = sub_2 + sub_3 + sub_4

	print((total * (total - 1) - (total * sub_tot%mod))%mod)
	# print ((total)* (total - 1 - (((sub_3 + sub_2)%mod + (sub_4_4 +sub_4_3)%mod)%mod + sub_4_2%mod)))% mod 

import math
def combi(a,b):
	mod = 10**9 + 7
	if a < b:
		return 0
	if a == 1:
		return 1
	if b < a/2:
		b = a - b
	temp = 1
	for i in range(b + 1,a + 1):
		temp = (temp * i%mod)%mod
	temp /= math.factorial(a - b)
	return temp
for _ in range(eval(input())):
	mod = 10**9 + 7
	string1 = input()
	n = len(string1)
	dict1 = {}
	count = 0
	alpha = set()
	for ele in string1:
		if ele in dict1:
			dict1[ele] += 1
		else:
			dict1[ele] = 1
			alpha.add(ele)
			count += 1
 
	count_list = []
	total = 1
	rem = n
	for ele in alpha:
		total = (total % mod) * (combi(rem,dict1[ele]) % mod)%mod
		rem -= dict1[ele]
		count_list.append(dict1[ele])
 
	sum_list = [n - count_list[0]]
	for i in range(1,count):
		sum_list.append(sum_list[i - 1] - count_list[i])
 
	sub_2 = 0
	sub = 0
	for i in count_list:
		sub_2 += (n - i) * i
	sub_2 /= 2
	# print sub_2
 
	sub_3 = 0
	for i in range(count):
		for j in range(i + 1,count):
			sub_3 += count_list[i] * count_list[j] * sum_list[j]
 
	sub_3 = 2 * sub_3
 
	sub_4_4 = 0
	for i in range(count):
		for j in range(i + 1,count):
			for k in range(j + 1,count):
				sub_4_4 += count_list[i] * count_list[j] * count_list[k] * sum_list[k]
 
	sub_4_4 *= 3
	sub_4_2 = 0
	for i in range(count):
		for j in range(i + 1,count):
			sub_4_2 += (count_list[i] * (count_list[i] - 1) * count_list[j] * (count_list[j] - 1))/4
 
	sub_4_3 = 0
	for i in range(count):
		temp = 0
		for j in range(count):
			if j != i:
				temp += count_list[j] * (n - count_list[i] - count_list[j])
		temp /= 2
		sub_4_3 += ((count_list[i] * (count_list[i] - 1)) * temp)/2
		# print sub_4_3
	sub_4_3 *= 2
	sub_4 = ((sub_4_2%mod + sub_4_3%mod) + sub_4_4%mod)%mod
	sub_tot = ((sub_2%mod + sub_3%mod)%mod + sub_4%mod)%mod

	print(((total * (total - 1))% mod - (total * sub_tot)%mod)%mod)
	# print ((total)* (total - 1 - (((sub_3 + sub_2)%mod + (sub_4_4 +sub_4_3)%mod)%mod + sub_4_2%mod)))% mod 

import math
def combi(a,b):
	mod = 10**9 + 7
	if a < b:
		return 0
	if a == 1:
		return 1
	if b < a/2:
		b = a - b
	temp = 1
	for i in range(b + 1,a + 1):
		temp = (temp * i%mod)%mod
	temp /= math.factorial(a - b)
	return temp
for _ in range(eval(input())):
	mod = 10**9 + 7
	string1 = input()
	n = len(string1)
	dict1 = {}
	count = 0
	alpha = set()
	for ele in string1:
		if ele in dict1:
			dict1[ele] += 1
		else:
			dict1[ele] = 1
			alpha.add(ele)
			count += 1
 
	count_list = []
	total = 1
	rem = n
	for ele in alpha:
		total = (total % mod) * (combi(rem,dict1[ele]) % mod)%mod
		rem -= dict1[ele]
		count_list.append(dict1[ele])
 
	sum_list = [n - count_list[0]]
	for i in range(1,count):
		sum_list.append(sum_list[i - 1] - count_list[i])
 
	sub_2 = 0
	sub = 0
	for i in count_list:
		sub_2 += (n - i) * i
	sub_2 /= 2
	# print sub_2
 
	sub_3 = 0
	for i in range(count):
		for j in range(i + 1,count):
			sub_3 += count_list[i] * count_list[j] * sum_list[j]
 
	sub_3 = 2 * sub_3
 
	sub_4_4 = 0
	for i in range(count):
		for j in range(i + 1,count):
			for k in range(j + 1,count):
				sub_4_4 += count_list[i] * count_list[j] * count_list[k] * sum_list[k]
 
	sub_4_4 *= 3
	sub_4_2 = 0
	for i in range(count):
		for j in range(i + 1,count):
			sub_4_2 += (count_list[i] * (count_list[i] - 1) * count_list[j] * (count_list[j] - 1))/4
 
	sub_4_3 = 0
	for i in range(count):
		temp = 0
		for j in range(count):
			if j != i:
				temp += count_list[j] * (n - count_list[i] - count_list[j])
		temp /= 2
		sub_4_3 += ((count_list[i] * (count_list[i] - 1)) * temp)/2
		# print sub_4_3
	sub_4_3 *= 2
	print(((total)* (total - 1 - (((sub_3 + sub_2)%mod + (sub_4_4 +sub_4_3)%mod)%mod + sub_4_2%mod)))% mod) 

import math
def combi(a,b):
	if a < b:
		return 0
	if a == 1:
		return 1
	if b < a/2:
		b = a - b
	temp = 1
	for i in range(b + 1,a + 1):
		temp *= i
	temp /= math.factorial(a - b)
	return temp
for _ in range(eval(input())):
	mod = 10**9 + 7
	string1 = input()
	n = len(string1)
	dict1 = {}
	count = 0
	alpha = set()
	for ele in string1:
		if ele in dict1:
			dict1[ele] += 1
		else:
			dict1[ele] = 1
			alpha.add(ele)
			count += 1
 
	count_list = []
	total = 1
	rem = n
	for ele in alpha:
		total = (total % mod) * (combi(rem,dict1[ele]) % mod)%mod
		rem -= dict1[ele]
		count_list.append(dict1[ele])
 
	sum_list = [n - count_list[0]]
	for i in range(1,count):
		sum_list.append(sum_list[i - 1] - count_list[i])
 
	sub_2 = 0
	sub = 0
	for i in count_list:
		sub_2 += (n - i) * i
	sub_2 /= 2
	# print sub_2
 
	sub_3 = 0
	for i in range(count):
		for j in range(i + 1,count):
			sub_3 = ((count_list[i] * count_list[j] * sum_list[j])%mod + sub_3)%mod
 
	sub_3 = 2 * sub_3
 
	sub_4_4 = 0
	for i in range(count):
		for j in range(i + 1,count):
			for k in range(j + 1,count):
				sub_4_4 = (sub_4_4  +((count_list[i] * count_list[j])%mod * (count_list[k] * sum_list[k])%mod)%mod)%mod
 
	sub_4_4 *= 3
	sub_4_2 = 0
	for i in range(count):
		for j in range(i + 1,count):
			sub_4_2 = (sub_4_2 + ((count_list[i] * (count_list[i] - 1))%mod * (count_list[j] * (count_list[j] - 1))%mod/4))%mod
 
	sub_4_3 = 0
	for i in range(count):
		temp = 0
		for j in range(count):
			if j != i:
				temp = (temp + (count_list[j] * (n - count_list[i] - count_list[j]))%mod)%mod
		temp /= 2
		sub_4_3 = ((((count_list[i] * (count_list[i] - 1)) * temp)/2)%mod + sub_4_3)%mod
		# print sub_4_3
	sub_4_3 *= 2
	sub_4_3 %= mod
	print(((total)* (total - 1 - (((sub_3 + sub_2)%mod + (sub_4_4 +sub_4_3)%mod)%mod + sub_4_2%mod)))% mod) 

import math
def combi(a,b):
	if a < b:
		return 0
	if a == 1:
		return 1
	if b < a/2:
		b = a - b
	temp = 1
	for i in range(b + 1,a + 1):
		temp *= i
	temp /= math.factorial(a - b)
	return temp
for _ in range(eval(input())):
	mod = 10**9 + 7
	string1 = input()
	n = len(string1)
	dict1 = {}
	count = 0
	alpha = set()
	for ele in string1:
		if ele in dict1:
			dict1[ele] += 1
		else:
			dict1[ele] = 1
			alpha.add(ele)
			count += 1
 
	count_list = []
	total = 1
	rem = n
	for ele in alpha:
		total = (total % mod) * (combi(rem,dict1[ele]) % mod)%mod
		rem -= dict1[ele]
		count_list.append(dict1[ele])
 
	sum_list = [n - count_list[0]]
	for i in range(1,count):
		sum_list.append(sum_list[i - 1] - count_list[i])
 
	sub_2 = 0
	sub = 0
	for i in count_list:
		sub_2 += (n - i) * i
	sub_2 /= 2
	# print sub_2
 
	sub_3 = 0
	for i in range(count):
		for j in range(i + 1,count):
			sub_3 += count_list[i] * count_list[j] * sum_list[j]
 
	sub_3 = 2 * sub_3
 
	sub_4_4 = 0
	for i in range(count):
		for j in range(i + 1,count):
			for k in range(j + 1,count):
				sub_4_4 += count_list[i] * count_list[j] * count_list[k] * sum_list[k]
 
	sub_4_4 *= 3
	sub_4_2 = 0
	for i in range(count):
		for j in range(i + 1,count):
			sub_4_2 += (count_list[i] * (count_list[i] - 1) * count_list[j] * (count_list[j] - 1))/4
 
	sub_4_3 = 0
	for i in range(count):
		temp = 0
		for j in range(count):
			if j != i:
				temp += count_list[j] * (n - count_list[i] - count_list[j])
		temp /= 2
		sub_4_3 += ((count_list[i] * (count_list[i] - 1)) * temp)/2
		# print sub_4_3
	sub_4_3 *= 2
	print(((total)* (total - 1 - (((sub_3 + sub_2)%mod + (sub_4_4 +sub_4_3)%mod)%mod + sub_4_2%mod)))% mod) 

import math
def combi(a,b):
	if a < b:
		return 0
	if a == 1:
		return 1
	if b < a/2:
		b = a - b
	temp = 1
	for i in range(b + 1,a + 1):
		temp *= i
	temp /= math.factorial(a - b)
	return temp
for _ in range(eval(input())):
	mod = 10**9 + 7
	string1 = input()
	n = len(string1)
	dict1 = {}
	count = 0
	alpha = set()
	for ele in string1:
		if ele in dict1:
			dict1[ele] += 1
		else:
			dict1[ele] = 1
			alpha.add(ele)
			count += 1

	count_list = []
	total = 1
	rem = n
	for ele in alpha:
		total = (total % mod) * (combi(rem,dict1[ele]) % mod)%mod
		rem -= dict1[ele]
		count_list.append(dict1[ele])

	sum_list = [n - count_list[0]]
	for i in range(1,count):
		sum_list.append(sum_list[i - 1] - count_list[i])

	sub_2 = 0
	sub = 0
	for i in count_list:
		sub_2 += (n - i) * i
	sub_2 /= 2
	# print sub_2

	sub_3 = 0
	for i in range(count):
		for j in range(i + 1,count):
			sub_3 += count_list[i] * count_list[j] * sum_list[j]

	sub_3 = 2 * sub_3

	sub_4_4 = 0
	for i in range(count):
		for j in range(i + 1,count):
			for k in range(j + 1,count):
				sub_4_4 += count_list[i] * count_list[j] * count_list[k] * sum_list[k]

	sub_4_4 *= 3
	sub_4_2 = 0
	for i in range(count):
		for j in range(i + 1,count):
			sub_4_2 += (count_list[i] * (count_list[i] - 1) * count_list[j] * (count_list[j] - 1))/4

	sub_4_3 = 0
	for i in range(count):
		temp = 0
		for j in range(count):
			if j != i:
				temp += count_list[j] * (n - count_list[i] - count_list[j])
		temp /= 2
		sub_4_3 += ((count_list[i] * (count_list[i] - 1)) * temp)/2
		# print sub_4_3
	sub_4_3 *= 2
	# for i in range(count):
	# 	sub_4_3 += (count_list[i] * (count_list[i] - 1)) * (n - count_list[i])

	# print total
	# print sub_2
	# print sub_3
	# print sub_4_2
	# print sub_4_3
	# print sub_4_4
	print(((total)* (total - sub_3 - sub_2 - sub_4_4 -sub_4_3- sub_4_2-1))% mod)

from collections import Counter

class FastScanner:
    def __init__(self):
        import sys
        self.inp = sys.stdin.read().split()
        self.readAt = -1
    def nextInt(self):
        self.readAt += 1
        return int(self.inp[self.readAt])
    def nextString(self):
        self.readAt += 1
        return self.inp[self.readAt]
    def nextRange(self, n):
        self.readAt += n
        return self.inp[self.readAt-n+1:self.readAt+1]
    def skip(self, n):
        self.readAt += n
 
class PrintWriter:
    def __init__(self):
        self.pw = []
    def println(self, n):
        self.pw.append(n)
    def flush(self):
        print("\n".join(map(str, self.pw)))
        self.pw = []

class Factorial:
    def __init__(self, limit, MOD):
        self.fac = [1]
        for i in range(1, limit+1):
            self.fac.append((i*self.fac[-1]) % MOD)
    def __getitem__(self, n):
        return self.fac[n]

def modInverse(n, p):
    return pow(n, p-2, p)

def nCr(n, r, f, MOD):
    if r>n: return 0
    x = f[n] % MOD
    y = f[r] % MOD
    z = f[n-r] % MOD
    return (x * modInverse(y, MOD) * modInverse(z, MOD)) % MOD

def main():
    MOD = 1000000007
    limit = 100000
    fs = FastScanner()
    pw = PrintWriter()
    f = Factorial(limit, MOD)
    t = fs.nextInt()
    for i in range(t):
        A = fs.nextString()
        n = len(A)
        mapp = Counter(A)
        combs = f[n]
        sim2 = nCr(n, 2, f, MOD)
        sim3 = nCr(n, 3, f, MOD)
        sim4 = nCr(n, 4, f, MOD) * 3
        nm2c2 = nCr(n-2, 2, f, MOD)
        for i in mapp:
            combs = (combs * modInverse(f[mapp[i]], MOD)) % MOD
            ncr2 = nCr(mapp[i], 2, f, MOD)
            rest = n - mapp[i]
            sim2 -= ncr2
            sim3 -= ncr2*rest
            sim4 -= ((nm2c2 * ncr2) % MOD)
            ncr3 = nCr(mapp[i], 3, f, MOD)
            sim3 -= ncr3
            ncr4 = nCr(mapp[i], 4, f, MOD)
            sim4 += ((ncr4 * 3) % MOD)
        summ = ((combs * (combs-1)) % MOD)
        sim2 = ((combs * sim2 * 1) % MOD)
        sim3 = ((combs * sim3 * 2) % MOD)
        sim4 = ((combs * sim4) % MOD)
        pw.println((summ - (sim2 + sim3 + sim4)) % MOD)
    pw.flush()

def __starting_point():
    main()

__starting_point()

import sys
def extended_gcd(aa, bb):
    lastremainder, remainder = abs(aa), abs(bb)
    x, lastx, y, lasty = 0, 1, 1, 0
    while remainder:
        lastremainder, (quotient, remainder) = remainder, divmod(lastremainder, remainder)
        x, lastx = lastx - quotient*x, x
        y, lasty = lasty - quotient*y, y
    return lastremainder, lastx * (-1 if aa < 0 else 1), lasty * (-1 if bb < 0 else 1)
def modinv(a, m):
	g, x, y = extended_gcd(a, m)
	if g != 1:
		raise ValueError
	return x % m
aa,bb,mod=500,300,10**9+7
fact=[1]
for i in range(1,pow(10,5)+10):
    fact.append((fact[i-1]*i)%mod)
for _ in range(int(sys.stdin.readline())):
    s=list(map(str,sys.stdin.readline().split()))[0]
    ch=[0]*26
    for i in s:
        ch[ord(i)-97]+=1
    n=len(s)
    ans,zero=0,1
    total=fact[n]
    for i in range(26):
        if ch[i]>0:
            total=(total*modinv(fact[ch[i]],mod))%mod
    for i in range(26):
        if ch[i]>0:
            for j in range(i+1,26):
                if ch[j]>0:
                    ans=(ans+ch[i]*ch[j])%mod
                    ans=(ans+((((((ch[i]*ch[j]%mod)*(ch[i]-1)%mod)*(ch[j]-1))%mod)*250000002)%mod))%mod
                    for k in range(j+1,26):
                        if ch[k]>0:
                            ans=(ans+(((ch[i]*ch[j]%mod)*ch[k]%mod)*2)%mod)%mod
                            ans=(ans+(((ch[i]*ch[j]%mod)*ch[k]%mod)*(ch[i]-1))%mod)%mod
                            ans=(ans+(((ch[i]*ch[j]%mod)*ch[k]%mod)*(ch[j]-1))%mod)%mod
                            ans=(ans+(((ch[i]*ch[j]%mod)*ch[k]%mod)*(ch[k]-1))%mod)%mod
                            for l in range(k+1,26):
                                if ch[l]>0:
                                    ans=(ans+(((((ch[i]*ch[j]%mod)*ch[k]%mod)*ch[l])%mod)*3)%mod)%mod
    print((pow(total,2,mod)-((ans+zero)%mod*total%mod)%mod)%mod)

M=1000000007
def f(n,r):
	if n==0:
		return 0
	if (r>n/2) :
		r=n-r
	if r==0:
		return 1
	if r>n :
		return 0
	a=1
	j=2
	for i in range(0,r):
		a=a*n
		n=n-1
		while(a%j==0 and j<=r):
			a=a/j
			j=j+1
	return a%M
T=int(eval(input()))
for i in range(0,T):
	A=input()
	a = [0 for i in range(0,26)]
	for letter in A:
		a[ord(letter)-ord('a')]=a[ord(letter)-ord('a')]+1
	nways=1
	k=len(A)
	for i in range(0,26):
		nways = (nways * f(k,a[i]))%M
		k=k-a[i]
		if k==0:
			break
	d2=0
	d3=0
	d4=0
	d211=0
	d22=0
	for i in range(0,26):
		for j in range(i+1,26):
			d2 = (d2 + ((a[i]*a[j])%M) )%M
			d22 = (d22 + ((f(a[i],2)*f(a[j],2))%M) )%M
			for k in range(j+1,26):
				d3 = (d3 + (( a[k]*((a[i]*a[j])%M) )%M) )%M
				d211 = (d211 + (( f(a[k],2)*((a[i]*a[j])%M) )%M) )%M
				d211 = (d211 + (( f(a[j],2)*((a[k]*a[i])%M) )%M) )%M
				d211 = (d211 + (( f(a[i],2)*((a[j]*a[k])%M) )%M) )%M
				for l in range(k+1,26):
					d4 = (d4 + (( ((a[i]*a[j])%M) * ((a[k]*a[l])%M) )%M) )%M
	ans = (1 + d2 + (d3*2) + (d4*3) + (d211*2) + d22 )%M
	ans = (nways - ans + M)%M
	ans = (nways * ans)%M
	print(ans)

from math import factorial as ff
from itertools import permutations as p
from itertools import combinations as cc
a=ff(4)%10
author='biggy_bs'
def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)
 
def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m
def factorialMod(n, modulus):
    ans=1
    l=[]
    if n <= modulus//2:
        #calculate the factorial normally (right argument of range() is exclusive)
        for i in range(1,n+1):
            ans = (ans * i) % modulus
            l.append(ans)
    return l
def precomputation():
    nC2=[0]*100002
    nC3=[0]*100002
    nC4=[0]*100002
    for i in range(100002):
        if i>=1:
            nC2[i]=((i)*(i-1))/2
        else:
            nC2[i]=0
        if i>=2:
            nC3[i]=(i*(i-1)*(i-2))/6
        else:
            nC3[i]=0
        if i>=3:
            nC4[i]=(i*(i-1)*(i-2)*(i-3))/24
        else:
            nC4[i]=0
    return (nC2,nC3,nC4)
def count_two(arr,mod):
    ans=0
    for i in range(26):
        if arr[i]==0:
            continue
        for j in range(i+1,26):
            if arr[j]==0:
                continue
            ans=(ans+arr[i]*arr[j])%mod
            ans=(ans+((((((arr[i]*arr[j]%mod)*(arr[i]-1)%mod ) * (arr[j]-1))%mod) * modinv(4,mod))%mod))%mod
            for k in range(j+1,26):
                if arr[k]==0:
                    continue
                ans=(ans +(((arr[i]*arr[j]%mod)*arr[k]%mod)*2)%mod)%mod
                ans=(ans +(((arr[i]*arr[j]%mod)*arr[k]%mod)*(arr[i]-1))%mod)%mod
                ans=(ans +(((arr[i]*arr[j]%mod)*arr[k]%mod)*(arr[j]-1))%mod)%mod
                ans=(ans +(((arr[i]*arr[j]%mod)*arr[k]%mod)*(arr[k]-1))%mod)%mod
                for l in range(k+1,26):
                    if arr[l]==0:
                        continue
                    ans=(ans+(((((arr[i]*arr[j]%mod)*arr[k]%mod)*arr[l])%mod)*3)%mod)%mod
    return ans
                      
mod=10**9+7
fact=factorialMod(100002,mod)
pre=precomputation()
nC2=pre[0]
nC3=pre[1]
nC4=pre[2]
f=[0]*100002
t=eval(input());dic={}
while t>0:
    t-=1
    s=input()
    len_s=len(s)
    dic={}
    arr=[0]*26
    for i in s:
        try:
            dic[i]+=1
        except:
            dic[i]=1
    for i in s:
        arr[ord(i)-97]+=1
    answer_two=count_two(arr,mod)
    answer_two=(answer_two%mod + 1%mod)%mod
    count_one=0
    for i in range(26):
        try:
            qww=dic[chr(i+97)]%mod
            for j in range(i+1,26):
                try:
                    count_one=(count_one%mod + qww*dic[chr(j+97)]%mod)%mod
                except:
                    break
        except:
            break
    xxx=fact[len_s-1]%mod
    for i in dic:
        xxx=(xxx%mod * modinv(fact[dic[i]-1]%mod,mod))%mod
    ans=(xxx*xxx)%mod
    #print count_one
    zero=xxx
    one=(xxx * count_one%mod)%mod
    if len(dic)==len_s:
        aa=len_s-2
        two=(aa%mod * (aa+1)%mod *(aa+2)%mod * (3*aa + 5)%mod * modinv(24,mod))%mod
        #print two
    elif len(dic)==2 and ((dic[s[0]]==1) or dic[s[0]]==len_s-1 or dic[s[0]]==len_s):
        two=0
    else:
        two=1
    two=(two%mod * xxx)%mod
    answer_two=(answer_two%mod * xxx%mod)%mod
    ct=0
    if len_s<=3:
        print(0)
    else:
        print((ans-(answer_two)%mod)  % mod)  


from math import factorial as ff
from itertools import permutations as p
from itertools import combinations as cc
a=ff(4)%10
author='biggy_bs'
def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)
 
def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m
def factorialMod(n, modulus):
    ans=1
    l=[]
    if n <= modulus//2:
        #calculate the factorial normally (right argument of range() is exclusive)
        for i in range(1,n+1):
            ans = (ans * i) % modulus
            l.append(ans)
    return l
def precomputation():
    nC2=[0]*100002
    nC3=[0]*100002
    nC4=[0]*100002
    for i in range(100002):
        if i>=1:
            nC2[i]=((i)*(i-1))/2
        else:
            nC2[i]=0
        if i>=2:
            nC3[i]=(i*(i-1)*(i-2))/6
        else:
            nC3[i]=0
        if i>=3:
            nC4[i]=(i*(i-1)*(i-2)*(i-3))/24
        else:
            nC4[i]=0
    return (nC2,nC3,nC4)
def count_two(arr,mod):
    ans=0
    for i in range(26):
        if arr[i]==0:
            continue
        for j in range(i+1,26):
            if arr[j]==0:
                continue
            ans=(ans+arr[i]*arr[j])%mod
            ans=(ans+((((((arr[i]*arr[j]%mod)*(arr[i]-1)%mod ) * (arr[j]-1))%mod) * modinv(4,mod))%mod))%mod
            for k in range(j+1,26):
                if arr[k]==0:
                    continue
                ans=(ans +(((arr[i]*arr[j]%mod)*arr[k]%mod)*2)%mod)%mod
                ans=(ans +(((arr[i]*arr[j]%mod)*arr[k]%mod)*(arr[i]-1))%mod)%mod
                ans=(ans +(((arr[i]*arr[j]%mod)*arr[k]%mod)*(arr[j]-1))%mod)%mod
                ans=(ans +(((arr[i]*arr[j]%mod)*arr[k]%mod)*(arr[k]-1))%mod)%mod
                for l in range(k+1,26):
                    if arr[l]==0:
                        continue
                    ans=(ans+(((((arr[i]*arr[j]%mod)*arr[k]%mod)*arr[l])%mod)*3)%mod)%mod
    return ans
                      
mod=10**9+7
fact=factorialMod(100002,mod)
pre=precomputation()
nC2=pre[0]
nC3=pre[1]
nC4=pre[2]
f=[0]*100002
t=eval(input());dic={}
while t>0:
    t-=1
    s=input()
    len_s=len(s)
    if len_s>100:
        pass
    dic={}
    arr=[0]*26
    for i in s:
        try:
            dic[i]+=1
        except:
            dic[i]=1
    for i in s:
        arr[ord(i)-97]+=1
    answer_two=count_two(arr,mod)
    answer_two=(answer_two%mod + 1%mod)%mod
    count_one=0
    for i in range(26):
        try:
            qww=dic[chr(i+97)]%mod
            for j in range(i+1,26):
                try:
                    count_one=(count_one%mod + qww*dic[chr(j+97)]%mod)%mod
                except:
                    break
        except:
            break
    xxx=fact[len_s-1]%mod
    for i in dic:
        xxx=(xxx%mod * modinv(fact[dic[i]-1]%mod,mod))%mod
    ans=(xxx*xxx)%mod
    #print count_one
    zero=xxx
    one=(xxx * count_one%mod)%mod
    if len(dic)==len_s:
        aa=len_s-2
        two=(aa%mod * (aa+1)%mod *(aa+2)%mod * (3*aa + 5)%mod * modinv(24,mod))%mod
        #print two
    elif len(dic)==2 and ((dic[s[0]]==1) or dic[s[0]]==len_s-1 or dic[s[0]]==len_s):
        two=0
    else:
        two=1
    two=(two%mod * xxx)%mod
    answer_two=(answer_two%mod * xxx%mod)%mod
    ct=0
    if len_s<=3:
        print(0)
    else:
        print((ans-(answer_two)%mod)  % mod)  


M=1000000007
def f(n,r):
	if n==0:
		return 0
	if r==0:
		return 1
	if r>n :
		return 0
	if (r>n/2) :
		r=n-r
	a=1
	j=2
	for i in range(0,r):
		a=a*n
		n=n-1
		while(a%j==0 and j<=r):
			a=a/j
			j=j+1
	return a%M
T=int(eval(input()))
for i in range(0,T):
	A=input()
	a = [0 for i in range(0,26)]
	for letter in A:
		a[ord(letter)-ord('a')]=a[ord(letter)-ord('a')]+1
	nways=1
	k=len(A)
	for i in range(0,26):
		nways = (nways * f(k,a[i]))%M
		k=k-a[i]
		if k==0:
			break
	d2=0
	d3=0
	d4=0
	d211=0
	d22=0
	for i in range(0,26):
		for j in range(i+1,26):
			d2 = (d2 + ((a[i]*a[j])%M) )%M
			d22 = (d22 + ((f(a[i],2)*f(a[j],2))%M) )%M
			for k in range(j+1,26):
				d3 = (d3 + (( a[k]*((a[i]*a[j])%M) )%M) )%M
				d211 = (d211 + (( f(a[k],2)*((a[i]*a[j])%M) )%M) )%M
				d211 = (d211 + (( f(a[j],2)*((a[k]*a[i])%M) )%M) )%M
				d211 = (d211 + (( f(a[i],2)*((a[j]*a[k])%M) )%M) )%M
				for l in range(k+1,26):
					d4 = (d4 + (( ((a[i]*a[j])%M) * ((a[k]*a[l])%M) )%M) )%M
	ans = (1 + d2 + (d3*2) + (d4*3) + (d211*2) + d22 )%M
	ans = (nways - ans + M)%M
	ans = (nways * ans)%M
	print(ans)

M=1000000007
def f(n,r):
	if n==0:
		return 0
	if r==0:
		return 1
	if r>n :
		return 0
	if (r>n/2) :
		r=n-r
	a=1;
	for i in range(0,r):
		a=a*n
		n=n-1
	for i in range(0,r):
		a=(a/(i+1))
	return a%M
T=int(eval(input()))
for i in range(0,T):
	A=input()
	a = [0 for i in range(0,26)]
	for letter in A:
		a[ord(letter)-ord('a')]=a[ord(letter)-ord('a')]+1
	nways=1
	k=len(A)
	for i in range(0,26):
		nways = (nways * f(k,a[i]))%M
		k=k-a[i]
		if k==0:
			break
	d2=0
	d3=0
	d4=0
	d211=0
	d22=0
	for i in range(0,26):
		for j in range(i+1,26):
			d2 = (d2 + ((a[i]*a[j])%M) )%M
			d22 = (d22 + ((f(a[i],2)*f(a[j],2))%M) )%M
			for k in range(j+1,26):
				d3 = (d3 + (( a[k]*((a[i]*a[j])%M) )%M) )%M
				d211 = (d211 + (( f(a[k],2)*((a[i]*a[j])%M) )%M) )%M
				d211 = (d211 + (( f(a[j],2)*((a[k]*a[i])%M) )%M) )%M
				d211 = (d211 + (( f(a[i],2)*((a[j]*a[k])%M) )%M) )%M
				for l in range(k+1,26):
					d4 = (d4 + (( ((a[i]*a[j])%M) * ((a[k]*a[l])%M) )%M) )%M
	ans = (1 + d2 + (d3*2) + (d4*3) + (d211*2) + d22 )%M
	ans = (nways - ans + M)%M
	ans = (nways * ans)%M
	print(ans)

def power(a,b):
    modu=1000000007
    res=1;
    while(b>0):
        if(b&1!=0):
            res=(res*a)%modu
        a=(a*a)%modu
        b>>=1
    return res
modu=1000000007
factorial=[0]*100010
factorial[0]=1
for i in range(1,100010):
    factorial[i]=(factorial[i-1]*i)%modu
test=int(input())
for tst in range(test):
    has=[0]*30
    st=input()
    for i in st:
        has[ord(i)-ord('a')]+=1
    neeche=1
    for i in range(26):
            neeche=(neeche*factorial[has[i]])%modu
    final=(factorial[len(st)]*power(neeche,modu-2))%modu
    minus=1
    for i in range(26):
            for j in range(i+1,26):
                minus=(minus+has[i]*has[j])%modu
    for i in range(26):
            for j in range(i+1,26):
                for k in range(j+1,26):
                    minus=(minus+has[i]*has[j]*has[k]*2)%modu
    mul =0
    for i in range(26):
            for j in range(i+1,26):
                for k in range(0,26):
                    if(k!=i and k!=j):
                        for l in range(k+1,26):
                            if(l!=i and l!=j):
                                mul=(mul+has[i]*has[j]*has[k]*has[l])%(2*modu);
                            
    mul/=2
    minus=(minus+mul)%modu
    mul=0
    for i in range(26):
            if(has[i]>1):
                for j in range(26):
                    if(j!=i):
                        for k in range(j+1,26):
                            if(k!=i):
                                mul=(mul+(has[i]*(has[i]-1)/2)*has[j]*has[k])%modu
    minus=(minus+mul*2)%modu
    mul=0
    for i in range(26):
            for j in range(i+1,26):
                if(has[i]>=2 and  has[j]>=2):
                            mul=(mul+((has[i]*(has[i]-1))/2)*((has[j]*(has[j]-1))/2))%modu
    minus=(minus+mul)%modu
    mul=final-minus
    if(mul<0):
            mul+=modu
    ans=(final*mul)%modu
    print(ans)
    

#pradeep singh NIT trichy
#pradeepsng30@yahoo.com

p=1000000007
mod=p;

def fact(n):
	f=1
	i=2
	while (i<=n):
		f=f*i
		f=f%mod
		i=i+1
	return f
		

def perm_count(orig_list, k):

	master_list  = []
	master_list.append(list(orig_list))
	while k > 0:
	    big_list = list(master_list) 
	    for each_list in big_list: 
	        for each_temp_list in permuter(each_list):
	            if each_temp_list not in master_list:
	                master_list.append(each_temp_list)
	                
	
	    k-=1
	
	total_count = len(master_list)
#	print sorted(master_list) #If you need a sanity check, feel free to leave out
	return total_count
	#end perm_count

def permuter(my_list):#returns a list of lists
    lists_list = []
   
    for i in range(len(my_list)):
        for j in range(len(my_list)):
            temp_list = my_list[:]
            if i != j:
                temp_list[i],temp_list[j] = temp_list[j],temp_list[i]
            if temp_list not in lists_list:
                lists_list.append(list(temp_list))

    return lists_list




def modInv(x):
	y = pow(x, p-2, p)
	return y
	


def numP(wordArray):

	letterOccurances = list()
# List of letters that have been counted in wordArray
	countedLetters = list()
	
	wordLength = len(wordArray)
	
	numerator = fact(wordLength)%mod
	
# Loops through wordArray, counts how many times a letter occurs, skips over
# already counted letters using a list of such letters (list updated each time) 
	for letter in wordArray:
	    if letter in countedLetters:
	        continue
	    letterOccurances.append(wordArray.count(letter))
	    countedLetters.append(letter)
	
	# Denominator of final formula
	denominator = 1
	ANS=1
	ANS=numerator
#	modInv(900)
#	print "here"
	for i in letterOccurances:
		ANS=ANS*modInv(fact(i))%mod
	    #denominator = (denominator * math.factorial(i))
	
	return ANS	
    	
    	
    
    
    
def ans(a):
#	print "here"
	if(len(a)<4):
		return 0
#	return 0
	mylist=list(a)
	n=numP(mylist)
#	n=24
	m=perm_count(mylist,2)%mod
	return (n*(n-m))%mod
	


t = int(input())
#print t

while (t>0):
	a=input()
#	print a
	print(ans(a))
	#print "\n"
	t=t-1
#print perm_count(D,2)

factorial, mod = [1], 10 ** 9 + 7
for i in range(1, 112345):
	factorial.append(factorial[-1] * i)
	factorial[-1] %= mod

for _ in range(eval(input())):
	X = [0 for i in range(26)]
	for x in input():
		X[ord(x) - ord('a')] += 1
	ans = 1
	for i in range(26):
		for j in range(i + 1, 26):
			ans += X[i] * X[j]
	for i in range(26):
		for j in range(i + 1, 26):
			for k in range(j + 1, 26):
				ans += X[i] * X[j] * X[k] * 2
	for i in range(26):
		for j in range(i + 1, 26):
			ans += (X[i] * (X[i] - 1) * X[j] * (X[j] - 1)) / 4
	for i in range(26):
		for j in range(i + 1, 26):
			for k in range(j + 1, 26):
				ans += ((X[i] * X[j] * X[k]) * (X[i] + X[j] + X[k] - 3))
	for i in range(26):
		for j in range(i + 1, 26):
			for k in range(j + 1, 26):
				for l in range(k + 1, 26):
					ans += X[i] * X[j] * X[k] * X[l] * 3
	stuff = factorial[sum(X)]
	for x in X:
		if x:
			stuff *= pow(factorial[x], mod - 2, mod)
	stuff %= mod
	print(stuff * (stuff - ans) % mod)

	

from math import factorial as ff
from itertools import permutations as p
from itertools import combinations as cc
a=ff(4)%10
author='biggy_bs'
def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m
def factorialMod(n, modulus):
    ans=1
    if n <= modulus//2:
        #calculate the factorial normally (right argument of range() is exclusive)
        for i in range(1,n+1):
            ans = (ans * i) % modulus   
    else:
        #Fancypants method for large n
        for i in range(1,modulus-n):
            ans = (ans * i) % modulus
        ans = modinv(ans, modulus)
 
        #Since m is an odd-prime, (-1)^(m-n) = -1 if n is even, +1 if n is odd
        if n % 2 == 0:
            ans = -1*ans + modulus
    return ans % modulus
mod=10**9+7

t=eval(input());dic={}
while t>0:
    t-=1
    s=input()
    if len(s)<=100:
        uy=''
        for i in range(len(s)):
            uy+=str(i)
        #xxx=p(s,len(s))
        xxc=cc(uy,2)
        rtt=[]
        for i in xxc:
            rtt.append(i)
        a=[]
        #for i in xxx:
        #    a.append(''.join(i))
        #a=set(a)
        #a=list(a)
        ans_ct=0
        s=list(s)
        flag=0
        lul=[]
        for ii in rtt:
            temp1=s[:]
            temp1[int(ii[0])],temp1[int(ii[1])]=temp1[int(ii[1])],temp1[int(ii[0])]
            lul.append(''.join(temp1))
            for jj in rtt:
                temp2=temp1[:]
                temp2[int(jj[0])],temp2[int(jj[1])]=temp2[int(jj[1])],temp2[int(jj[0])]
                lul.append(''.join(temp2))
        #print ans_ct
        ans_ct=len(set(lul))
        dic={}
        for i in s:
            try:
                dic[i]+=1
            except:
                dic[i]=1
        xxx=factorialMod(len(s),mod)
        for i in dic:
            xxx=(xxx%mod * modinv(factorialMod(dic[i],mod),mod))%mod
        ans=(xxx*xxx)%mod
        ct=0
        if len(s)<=3:
            print(0)
        else:
            print((ans-(ans_ct*xxx)%mod)  % mod)  


from math import factorial as ff
from itertools import permutations as p
from itertools import combinations as cc
a=ff(4)%10
author='biggy_bs'
def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m
def factorialMod(n, modulus):
    ans=1
    if n <= modulus//2:
        #calculate the factorial normally (right argument of range() is exclusive)
        for i in range(1,n+1):
            ans = (ans * i) % modulus   
    else:
        #Fancypants method for large n
        for i in range(1,modulus-n):
            ans = (ans * i) % modulus
        ans = modinv(ans, modulus)
 
        #Since m is an odd-prime, (-1)^(m-n) = -1 if n is even, +1 if n is odd
        if n % 2 == 0:
            ans = -1*ans + modulus
    return ans % modulus
mod=10**9+7

t=eval(input());dic={}
while t>0:
    t-=1
    s=input()
    if len(s)<=10:
        uy=''
        for i in range(len(s)):
            uy+=str(i)
        #xxx=p(s,len(s))
        xxc=cc(uy,2)
        rtt=[]
        for i in xxc:
            rtt.append(i)
        a=[]
        #for i in xxx:
        #    a.append(''.join(i))
        #a=set(a)
        #a=list(a)
        ans_ct=0
        s=list(s)
        flag=0
        lul=[]
        for ii in rtt:
            temp1=s[:]
            temp1[int(ii[0])],temp1[int(ii[1])]=temp1[int(ii[1])],temp1[int(ii[0])]
            lul.append(''.join(temp1))
            for jj in rtt:
                temp2=temp1[:]
                temp2[int(jj[0])],temp2[int(jj[1])]=temp2[int(jj[1])],temp2[int(jj[0])]
                lul.append(''.join(temp2))
        #print ans_ct
        ans_ct=len(set(lul))
        dic={}
        for i in s:
            try:
                dic[i]+=1
            except:
                dic[i]=1
        xxx=factorialMod(len(s),mod)
        for i in dic:
            xxx=(xxx%mod * modinv(factorialMod(dic[i],mod),mod))%mod
        ans=(xxx*xxx)%mod
        ct=0
        if len(s)<=3:
            print(0)
        else:
            print((ans-(ans_ct*xxx)%mod)  % mod)  


def exp(a,p,m):
    ans = 1
    while(p!=0):
        if(p%2==1):
            ans*=a
            ans%=mod
        a*=a
        a%=mod
        p>>=1
    return ans
mod = (10**9)+7
fact = [1]
for i in range(1,1+(10**5)):
    x = fact[-1]
    x = (x*i)%mod
    fact += [x]
inv_fact = []
for i in fact:
    x = exp(i,mod-2,mod)
    inv_fact += [x]
t = eval(input())
for _ in range(t):
    s = input()
    hs = [0]*26
    for i in s:
        x = ord(i) - 97
        hs[x]+=1
    l = len(s)
    tot_num = fact[l]
    for i in hs:
        tot_num *= inv_fact[i]
        tot_num %= mod
    xy = 1
    for i in range(26):
        for j in range(i+1,26):
            xy += (hs[i]*hs[j])
            xy %= mod
    for i in range(26):
        for j in range(i+1,26):
            for k in range(j+1,26):
                xy += (hs[i]*hs[j]*hs[k]*2)
                xy %= mod
    for i in range(26):
        for j in range(i+1,26):
            x = (hs[i]*(hs[i]-1))/2
            x %= mod
            y = (hs[j]*(hs[j]-1))/2
            y %= mod
            x*=y
            x%=mod
            xy+=x
            xy%=mod
    for i in range(26):
        for j in range(26):
            for k in range(j+1,26):
                if(i!=j and i!=k):
                    x = hs[i]*(hs[i]-1)
                    x%=mod
                    x*=hs[j]
                    x%=mod
                    x*=hs[k]
                    x%=mod
                    xy+=x
                    xy%=mod
    for a in range(26):
        for b in range(a+1,26):
            for c in range(b+1,26):
                for d in range(c+1,26):
                    x = (hs[a]*hs[b])%mod
                    x *= hs[c]
                    x %= mod
                    x *= hs[d]
                    x%=mod
                    x*=3
                    x%=mod
                    xy+=x
                    xy%=mod
    t1 = (tot_num*tot_num)%mod
    t2 = (tot_num *xy)%mod
    t1-=t2
    while(t1<0):
        t1+=mod
    print(t1)


import math
MAX=((10**9)+7)
t=int(input())
while t>0:
    x=input()
    d={};count=0
    l=len(x)
    for item in range(l):
        flag=0
        for i in d:
            if i==x[item]:
                flag=1
                d[i]+=1
                break
        if flag==0:
            d.fromkeys(x[item])
            d[x[item]]=1
    y=[]
    for item in d:
        y.append(d[item])
    prod=1
    q=len(y)
    for item in range(q):
        prod*=math.factorial(y[item])        
        if y[item]>1:
            count+=1
    def bruce():
        Sum2=0;Sum3=0;Sum4=0;Sum5=0;Sum6=0
        for i in range(q):
            temp3=0
            if y[i]>1:
                temp3=y[i]*((y[i]-1)/2)
            for j in range(i+1,q):
                temp1=0;temp2=0
                Sum2+=y[i]*y[j]
                if y[i]>1:
                    temp1=y[i]*(y[i]-1)/2
                if y[j]>1:
                    temp2=y[j]*(y[j]-1)/2
                Sum5+=temp1*temp2
                for k in range(j+1,q):
                    Sum3+=y[i]*y[j]*y[k]
                    #print y[i],y[j],y[k]
                    if y[i]>1:
                        Sum6+=(y[i]*(y[i]-1))/2*y[j]*y[k]
                        #print Sum6
                    if y[j]>1:
                        Sum6+=y[i]*(y[j]*(y[j]-1))/2*y[k]
                    #print Sum6
                    if y[k]>1:
                        Sum6+=y[i]*y[j]*(y[k]*(y[k]-1))/2
                    #print Sum6
                    for z in range(k+1,q):
                        Sum4+=y[i]*y[j]*y[k]*y[z]
        #print "Sum2=%d,Sum3=%d,Sum4=%d,Sum5=%d,Sum6=%d"%(Sum2,Sum3,Sum4,Sum5,Sum6)
        return ((Sum2%MAX+(Sum3*2)%MAX+(Sum4*3)%MAX+Sum5%MAX+(Sum6*2)%MAX))
    ans1=bruce()
    fact=math.factorial(l)
    #print "fact=%d,prod=%d"%(fact,prod)
    ast=fact/prod
    #print ast
    temp=(((ast)%MAX)*((ast-1)%MAX))%MAX
    RRR=((ast%MAX)*(ans1%MAX))%MAX
    ans=(temp-RRR+MAX)%MAX
    print(ans)
    t-=1