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: UNKNOWN_DIFFICULTY

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 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)
	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
	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
	sub_4_3 *= 2
	sub_4 = sub_4_3 + sub_4_4 + sub_4_2
	sub_tot = sub_2 + sub_3 + sub_4
	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
	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
	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)


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:
		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
	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
	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)


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)


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)
	return total_count

def permuter(my_list):
	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()
	countedLetters = list()
	wordLength = len(wordArray)
	numerator = fact(wordLength) % mod
	for letter in wordArray:
		if letter in countedLetters:
			continue
		letterOccurances.append(wordArray.count(letter))
		countedLetters.append(letter)
	denominator = 1
	ANS = 1
	ANS = numerator
	for i in letterOccurances:
		ANS = ANS * modInv(fact(i)) % mod
	return ANS

def ans(a):
	if len(a) < 4:
		return 0
	mylist = list(a)
	n = numP(mylist)
	m = perm_count(mylist, 2) % mod
	return n * (n - m) % mod
t = int(input())
while t > 0:
	a = input()
	print(ans(a))
	t = t - 1


(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:
		for i in range(1, n + 1):
			ans = ans * i % modulus
	else:
		for i in range(1, modulus - n):
			ans = ans * i % modulus
		ans = modinv(ans, modulus)
		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)
		xxc = cc(uy, 2)
		rtt = []
		for i in xxc:
			rtt.append(i)
		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))
		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]
					if y[i] > 1:
						Sum6 += y[i] * (y[i] - 1) / 2 * y[j] * y[k]
					if y[j] > 1:
						Sum6 += y[i] * (y[j] * (y[j] - 1)) / 2 * y[k]
					if y[k] > 1:
						Sum6 += y[i] * y[j] * (y[k] * (y[k] - 1)) / 2
					for z in range(k + 1, q):
						Sum4 += y[i] * y[j] * y[k] * y[z]
		return Sum2 % MAX + Sum3 * 2 % MAX + Sum4 * 3 % MAX + Sum5 % MAX + Sum6 * 2 % MAX
	ans1 = bruce()
	fact = math.factorial(l)
	ast = fact / prod
	temp = ast % MAX * ((ast - 1) % MAX) % MAX
	RRR = ast % MAX * (ans1 % MAX) % MAX
	ans = (temp - RRR + MAX) % MAX
	print(ans)
	t -= 1