Read problems statements in Mandarin Chinese, Russian and Vietnamese as well. 

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  (10^{9} + 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 (10^{9} + 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: HARD
Tags: Combinatorics

Starter code:

Solutions:
md = 10 ** 9 + 7
fact = []
prod = 1
for x in range(1, 100002):
	fact.append(prod)
	prod *= x
	prod %= md
for _ in range(int(input())):
	s = input()
	counts = [s.count(x) for x in set(s)]
	sym4 = 0
	sym3 = 0
	sym2 = 0
	sym1 = 0
	sym1choose2 = 0
	sym2choose2 = 0
	sym1cchoose2 = 0
	sym1c2choose2 = 0
	choose_all = fact[len(s)]
	for c in counts:
		choose2 = c * (c - 1) // 2
		sym4 += sym3 * c
		sym3 += sym2 * c
		sym2 += sym1 * c
		sym1 += c
		sym2choose2 += sym1choose2 * choose2
		sym1choose2 += choose2
		sym1cchoose2 += c * choose2
		sym1c2choose2 += c * c * choose2
		choose_all *= pow(fact[c], -1, md)
		choose_all %= md
	num_swap = sym2
	num_3_cycle = 2 * sym3
	num_2_swaps_abcd = 3 * sym4
	num_2_swaps_aabc = 2 * (sym1choose2 * sym2 - sym1cchoose2 * sym1 + sym1c2choose2)
	num_2_swaps_aabb = sym2choose2
	num_sim = 1 + num_swap + num_3_cycle + num_2_swaps_aabb + num_2_swaps_aabc + num_2_swaps_abcd
	num_sim %= md
	ans = choose_all * (choose_all - num_sim)
	ans %= md
	print(ans)


import sys
from collections import Counter, deque
from itertools import combinations

def read_ints(inp=sys.stdin):
	return list(map(int, next(inp).strip().split()))

def modfact(n, p, memo=[1]):
	if n <= 1:
		return 1
	lm = len(memo)
	if n < lm:
		return memo[n]
	f = memo[-1]
	for k in range(lm, n + 1):
		f = f * k % p
		memo.append(f)
	return f
M = 10 ** 9 + 7

def modinverse_p(a, p, memo={}):
	if a in memo:
		return memo[a]
	res = pow(a, p - 2, p)
	memo[a] = res
	return res

def sol1(S, M):
	cs = Counter(S)
	tt = modfact(len(S), M)
	for nb in cs.values():
		if nb > 1:
			tt *= modinverse_p(modfact(nb, M), M)
	r0 = 1
	r1 = sum((a * b for (a, b) in combinations(cs.values(), 2)))
	r2 = 0
	for (a, b, c, d) in combinations(cs.values(), 4):
		r2 = (r2 + 3 * a * b * c * d) % M
	for (a, b, c) in combinations(cs.values(), 3):
		if a > 1:
			r2 += 2 * a * (a - 1) // 2 * b * c
		if b > 1:
			r2 += 2 * b * (b - 1) // 2 * a * c
		if c > 1:
			r2 += 2 * c * (c - 1) // 2 * a * b
			r2 = r2 % M
	for (a, b) in combinations(cs.values(), 2):
		if a > 1 and b > 1:
			r2 += a * (a - 1) // 2 * b * (b - 1) // 2
	r3 = 2 * sum((a * b * c for (a, b, c) in combinations(cs.values(), 3)))
	pairs = (tt - r0 - r1 - r2 - r3) % M
	return tt * pairs % M
if 0:
	inp = iter('2\nabcd\nz\n'.split('\n'))
else:
	inp = sys.stdin
(T,) = read_ints(inp)
for _ in range(T):
	S = next(inp).strip()
	print(sol1(S, M))


md = 1000000007
mdinv = []
for i in range(5):
	mdinv.append(pow(i, md - 2, md))
from math import factorial

def modfactorial(n):
	res = 1
	while n > 1:
		res *= n
		res %= md
		n -= 1
	return res

def choose(n, m):
	if m > n:
		print('error', n, m)
		return -1
	if n == m:
		return 1
	res = 1
	if m > n / 2:
		m = n - m
	for k in range(n, n - m, -1):
		res *= k
		res %= md
	for k in range(1, m + 1):
		res *= mdinv[k]
		res %= md
	return res
for t in range(int(input())):
	s = input()
	n = len(s)
	if n <= 3:
		print(0)
	else:
		counts = dict()
		for c in s:
			if c in counts:
				counts[c] += 1
			else:
				counts[c] = 1
		counts = list(counts.values())
		counts.sort(reverse=True)
		if counts[0] >= len(mdinv):
			for i in range(len(mdinv), counts[0] + 1):
				mdinv.append(pow(i, md - 2, md))
		permstotal = modfactorial(n)
		for c in counts:
			if c == 1:
				break
			for i in range(c, 1, -1):
				permstotal *= mdinv[i]
				permstotal %= md
		_2s = choose(n, 2) % md
		for c in counts:
			if c == 1:
				break
			_2s -= choose(c, 2) % md
		_3s = choose(n, 3) % md
		for c in counts:
			if c == 1:
				break
			_3s -= (n - c) * choose(c, 2) % md
		for c in counts:
			if c < 3:
				break
			_3s -= choose(c, 3) % md
		_3s *= 2
		_4s = choose(n, 4) % md
		for c in counts:
			if c < 4:
				break
			_4s -= choose(c, 4) % md
		for c in counts:
			if c < 3:
				break
			_4s -= (n - c) * choose(c, 3) % md
		_2xs = 0
		for c in counts:
			if c < 2:
				break
			if n - c > 1:
				_2xs += choose(c, 2) * choose(n - c, 2) % md
		_4s -= _2xs
		_4s *= 3
		_4s += 2 * _2xs
		similars = (_2s + _3s + _4s + 1) % md
		dissimilars = permstotal - similars
		print(permstotal * dissimilars % md)