Chef has decided to retire and settle near a peaceful beach. He had always been interested in literature & linguistics. Now when he has leisure time, he plans to read a lot of novels and understand structure of languages. Today he has decided to learn a difficult language called Smeagolese. Smeagolese is an exotic  language whose alphabet is lowercase and uppercase roman letters. Also every word on this alphabet is a meaningful word in Smeagolese. Chef, we all know is a fierce learner - he has given himself a tough exercise. He has taken a word and wants to determine all possible anagrams of the word which mean something in Smeagolese.  Can you help him ?

-----Input-----
Input begins with a single integer T, denoting the number of test cases. After that T lines follow each containing a single string S - the word chef has chosen. You can assume that 1 <= T <= 500 and 1 <= |S| <= 500. You can also assume that no character repeats more than 10 times in the string. 

-----Output-----
Output one line per test case - the number of different words that are anagrams of the word that chef has chosen. As answer can get huge, print it modulo 10^9 + 7

-----Example-----
Input:
4
ab
aa
aA
AAbaz

Output:
2
1
2
60
Description:
In first case "ab" & "ba" are two different words. In third case, note that A & a are different alphabets and hence "Aa" & "aA" are different words.

Difficulty: MEDIUM_HARD
Tags: Number theory

Combinatorics

Mathematics

Starter code:

Solutions:
def fact(x):
	result = 1
	for i in range(2, x + 1):
		result *= i
	return result

def comb(n, k):
	if k > n - k:
		k = n - k
	result = 1
	for i in range(n - k + 1, n + 1):
		result *= i
	for i in range(1, k + 1):
		result //= i
	return result
n = int(input(''))
for i in range(n):
	s = input('')
	s = list(s)
	length = len(s)
	result = 1
	dict = {}
	for i in s:
		try:
			a = dict[i]
			dict[i] += 1
		except:
			dict[i] = 1
	sum = 0
	for i in dict.values():
		sum += i
		result *= comb(sum, i)
	print(result % (10 ** 9 + 7))


from math import factorial
t = int(input())
for i in range(t):
	s = input()
	hash = {}
	for j in s:
		try:
			hash[j]
		except:
			hash[j] = 1
		else:
			hash[j] += 1
	z = factorial(len(s))
	m = 10 ** 9 + 7
	k = 1
	for j in list(hash.keys()):
		k *= factorial(hash[j])
	print(z // k % m)


def factl(a):
	b = 1
	while a > 1:
		b *= a
		a -= 1
	return b
mdl = 1000000007
alph = 'abcdefghijklmnopqrstuvwxyz'
alph += alph.upper()
lct = list(map(lambda x: (x, 0), list(alph)))
for _ in range(int(input())):
	dct = dict(lct)
	ltrs = list(input().strip())
	for c in ltrs:
		dct[c] += 1
	prof = list(dct.values())
	prof.sort(reverse=True)
	perm = factl(sum(prof))
	for c in prof:
		if c < 2:
			break
		perm //= factl(c)
	print(perm % mdl)


import math
t = int(input())
mod = 1000000007
for _ in range(t):
	s = input()
	ans = math.factorial(len(s))
	d = dict()
	for i in s:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	for i in d:
		ans = ans // math.factorial(d[i])
	print(ans % mod)


mod = 1000000007

def fact(n):
	if n <= 1:
		return 1
	else:
		i = 1
		for p in range(2, n + 1):
			i *= p
		return i
for _ in range(int(input())):
	S = input()
	N = len(S)
	dic = {}
	for i in range(N):
		p = S[i]
		if p in dic.keys():
			dic[p] += 1
		else:
			dic[p] = 1
	f = fact(N)
	for t in dic.keys():
		f = f // fact(dic[t])
	print(f % mod)


from collections import Counter

def fact(num):
	factorial = 1
	for i in range(1, num + 1):
		factorial = factorial * i
	return factorial
t = int(input())
for _ in range(t):
	done = dict()
	strr = str(input())
	ans = fact(len(strr))
	res = Counter(strr)
	for i in res:
		done[i] = 0
	l = 1
	for i in res:
		if done[i] == 0:
			l = l * fact(res[i])
			done[i] = 1
	ans = ans // l
	ans = ans % 1000000007
	print(ans)


MOD = 1000000007
fact_mods = [0] * 501
(fact_mods[0], fact_mods[1]) = (1, 1)
for i in range(2, 501):
	fact_mods[i] = fact_mods[i - 1] * i % MOD
for _ in range(int(input())):
	s = input()
	n = len(s)
	counts = {}
	denom = 1
	for ch in s:
		counts[ch] = counts.get(ch, 0) + 1
	for ch in counts:
		denom = denom * fact_mods[counts[ch]] % MOD
	print(fact_mods[n] * pow(denom, MOD - 2, MOD) % MOD)


fact = [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800]
MOD = 1000000007

def fastExpo(base, exp):
	ans = 1
	base %= MOD
	while exp:
		if exp % 2:
			ans *= base
			ans %= MOD
		exp //= 2
		base *= base
		base %= MOD
	return ans
t = int(input())
for testcase in range(0, t):
	s = input()
	l = len(s)
	d = {}
	for c in s:
		if c in d.keys():
			d[c] += 1
		else:
			d[c] = 1
	den = 1
	for num in d.values():
		den *= fact[num]
	den = fastExpo(den, MOD - 2)
	numfact = 1
	for i in range(2, l + 1):
		numfact *= i
		numfact %= MOD
	ans = numfact * den % MOD
	print(ans)


t = int(input())
mod = 1000000007

def fac(num):
	if num == 1:
		return 1
	return num * fac(num - 1)
for _ in range(t):
	s = input()
	ans = fac(len(s))
	d = dict()
	for i in s:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	for i in d:
		if d[i] != 0:
			ans = ans // fac(d[i])
	print(ans % mod)


import math
t = int(input())
for i in range(t):
	s = input()
	l = list(s)
	seti = set(l)
	deno = 1
	for i in seti:
		deno *= math.factorial(l.count(i))
	leng = len(l)
	ans = math.factorial(leng) // deno % 1000000007
	print(int(ans))


def invmodp(a, p):
	r = a
	d = 1
	for count in range(p):
		d = (p // r + 1) * d % p
		r = d * a % p
		if r == 1:
			break
	else:
		raise ValueError('%d has no inverse mod %d' % (a, p))
	return d

def main():
	_mod = 10 ** 9 + 7
	f = [1]
	for i in range(1, 600):
		f.append(f[i - 1] * i % _mod)
	from collections import Counter
	import sys
	t = int(sys.stdin.readline().strip())
	for i in range(t):
		_list = sys.stdin.readline().strip()
		c = Counter(_list)
		_ans = f[len(_list)]
		c2 = Counter(c.values())
		for i in c2:
			k = invmodp(f[i], _mod)
			k2 = k
			for j in range(c2[i] - 1):
				k = k * k2 % _mod
			_ans = _ans * k % _mod
		print('%s' % _ans)
main()


from collections import Counter
mx = 502
f = [0] * mx
fi = [0] * mx
f[0] = 1
fi[0] = 1
m = 10 ** 9 + 7
for i in range(1, mx):
	f[i] = f[i - 1] * i % m
	fi[i] = fi[i - 1] * pow(i, m - 2, m) % m
for _ in range(int(input())):
	s = input()
	d = Counter(s).values()
	ans = f[len(s)]
	for x in d:
		ans *= fi[x]
		ans %= m
	print(ans)


import math
import os
for __ in range(int(input())):
	s = input()
	n = len(s)
	summ = math.factorial(n)
	l = []
	summ2 = 1
	for x in range(n):
		if s.count(s[x]) > 1 and s[x] not in l:
			summ2 = math.factorial(s.count(s[x]))
			summ //= summ2
			l.append(s[x])
	print(summ % 1000000007)


def pulverize(a, b):
	apair = [1, 0]
	bpair = [0, 1]
	while True:
		if a == 0:
			return (bpair[0], bpair[1])
		else:
			q = b // a
			b %= a
			bpair[0] -= apair[0] * q
			bpair[1] -= apair[1] * q
		if b == 0:
			return (apair[0], apair[1])
		else:
			q = a // b
			a %= b
			apair[0] -= bpair[0] * q
			apair[1] -= bpair[1] * q

def inverse(a, m):
	(x, k) = pulverize(a, m)
	g = a * x + m * k
	if g != 1:
		return 0
	if x < 0:
		x += m
	return x
mbase = 1000000007
fact = [1]
for i in range(500):
	fact.append((i + 1) * fact[i] % mbase)
t = int(input())
for it in range(t):
	s = sorted(input())
	cfreq = 1
	freqs = []
	for i in range(1, len(s)):
		if s[i] == s[i - 1]:
			cfreq += 1
		else:
			freqs.append(cfreq)
			cfreq = 1
	freqs.append(cfreq)
	den = 1
	for f in freqs:
		den *= fact[f]
		den %= mbase
	num = fact[len(s)]
	ans = num * inverse(den, mbase) % mbase
	print(ans)


def f(s):
	a = {}
	l = len(s)
	for i in s:
		a[i] = a.get(i, 0) + 1
	p = fact(l)
	for i in a:
		p //= fact(a[i])
	return p % 1000000007

def fact(n):
	p = 1
	for i in range(2, n + 1):
		p *= i
	return p
t = int(input())
for i in range(t):
	s = input()
	print(f(s))


mod = 10 ** 9 + 7
factorial = [1] + [0] * 500
for i in range(1, 501):
	factorial[i] = i * factorial[i - 1] % mod
for _ in range(int(input())):
	S = input()
	N = len(S)
	alphabet = [0] * 53
	for i in range(N):
		x = ord(S[i].lower()) - 97
		if S[i].isupper():
			x += 26
		alphabet[x] += 1
	sol = factorial[N]
	for i in alphabet:
		if i > 1:
			sol = pow(factorial[i], mod - 2, mod) * (sol % mod) % mod
	print(sol)


def fact(a):
	f = 1
	for i in range(2, a + 1):
		f = f * i
	return f
factorial = [1] * 11
d = 1
for k in range(1, 11):
	d = d * k
	factorial[k] = d

def main():
	t = int(input())
	for z in range(0, t):
		lis = [0] * 150
		st = input()
		for i in range(0, len(st)):
			lis[ord(st[i])] = lis[ord(st[i])] + 1
		denom = 1
		for j in range(0, 150):
			if lis[j] > 0:
				denom *= factorial[lis[j]]
		ans = fact(len(st)) // denom
		ans %= 1000000007
		print(ans)
main()


import math
for i in range(int(input())):
	s = input()
	freq = {}
	l = len(s)
	denom = 1
	ans = 0
	mod = 10 ** 9 + 7
	for x in s:
		if x in freq:
			freq[x] += 1
		else:
			freq[x] = 1
	for x in freq.keys():
		denom *= math.factorial(freq[x])
	print(math.factorial(l) // denom % mod)


def fact(n):
	ans = 1
	for j in range(1, n + 1):
		ans *= j
	return ans
test = int(input())
for i in range(test):
	s = input()
	dic = {}
	for i in s:
		if i in dic:
			dic[i] = dic[i] + 1
		else:
			dic[i] = 1
	ans = fact(len(s))
	for j in dic:
		ans = ans // fact(dic.get(j))
	print(ans % 1000000007)


from collections import defaultdict

def fac(num, modulo):
	ans = 1
	for i in range(2, num + 1):
		ans = ans * i % modulo
	return ans

def fast_expo(num, p, modulo):
	num %= modulo
	exxp = 1
	while p > 0:
		if p & 1:
			exxp = exxp * num % modulo
		num = num * num % modulo
		p >>= 1
	return exxp
modulo = 1000000007
t = int(input())
for i in range(t):
	s = input().strip()
	mp = defaultdict(int)
	for si in s:
		mp[si] += 1
	denom = 1
	for alpha in mp.keys():
		denom = denom * fac(mp[alpha], modulo)
	denom = fast_expo(denom, modulo - 2, modulo)
	nfac = fac(len(s), modulo)
	nfac = nfac * denom % modulo
	print(int(nfac))


import math

def find(s):
	l = len(s)
	dic = {}
	for j in s:
		if j not in dic:
			dic[j] = 1
		else:
			dic[j] += 1
	p = math.factorial(l)
	for j in dic:
		if dic[j] > 1:
			p = p // math.factorial(dic[j])
	print(p % (10 ** 9 + 7))
t = int(input())
for i in range(t):
	find(input())


dic = {0: 1, 1: 1}

def fact(n):
	if n in dic:
		return dic[n]
	else:
		dic[n] = n * fact(n - 1)
		return dic[n]
cases = int(input())
while cases > 0:
	cases -= 1
	s = input()
	out = fact(len(s))
	while len(s):
		c = s.count(s[0])
		s = s.replace(s[0], '')
		out //= fact(c)
	print(out % (10 ** 9 + 7))


t = int(input())

def fact(n):
	i = 1
	for j in range(2, n + 1):
		i *= j
	return i

def foo(word):
	t = {}
	for i in word:
		if i not in t:
			t[i] = 0
		t[i] = t[i] + 1
	initial = fact(len(word))
	for i in t:
		initial //= fact(t[i])
	print(initial % 1000000007)
while t != 0:
	t = t - 1
	word = input()
	foo(word)


a = pow(10, 9) + 7
import math
t = int(input())
for i in range(t):
	s = input()
	x = len(s)
	p = 1
	l = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z']
	for j in l:
		p = p * math.factorial(s.count(j))
	z = math.factorial(x) // p
	q = z % a
	print(q)


from math import factorial
from collections import Counter
from functools import reduce
import operator as op
mod = 1000000007
for _ in range(int(input())):
	s = input()
	c = Counter(s)
	num = factorial(len(s))
	den = 1
	for k in c:
		den *= factorial(c[k])
	print(num // den % mod)


e = 10 ** 9 + 7

def fact(n):
	ans = 1
	for i in range(2, n + 1):
		ans = ans * i % e
	return ans
t = int(input())
for _ in range(t):
	s = input()
	n = len(s)
	d = {}
	for i in s:
		try:
			d[i] += 1
		except:
			d[i] = 1
	x = fact(n)
	for i in d.values():
		y = fact(i)
		y = pow(y, e - 2, e)
		x = x * y % e
	print(x)


from math import *

def permRep(n):
	low = 1
	sum = 0
	for x in n:
		low *= factorial(x)
		sum += x
	return factorial(sum) // low % 1000000007

def isUpper(n):
	if n >= 'A' and n <= 'Z':
		return True
	return False
t = int(input())
while t > 0:
	t -= 1
	line = input()
	arr = [0] * 127
	for c in line:
		if isUpper(c):
			arr[ord(c)] += 1
		else:
			arr[ord(c)] += 1
	print(permRep(arr))


n = int(input())
Fac = [1]
p = 1
for i in range(1, 501):
	p *= i
	p %= 10 ** 9 + 7
	Fac.append(p)
for i in range(n):
	E = {}
	s = input()
	for item in s:
		if item in E:
			E[item] += 1
		else:
			E[item] = 1
	a = Fac[len(s)]
	b = 1
	for item in E:
		b *= Fac[E[item]]
		b %= 10 ** 9 + 7
	b = pow(b, 10 ** 9 + 5, 10 ** 9 + 7)
	print(a * b % (10 ** 9 + 7))


import math
mod = 10 ** 9 + 7
factorial = [1] + [0] * 500

def modInverse(b, m):
	g = math.gcd(b, m)
	return pow(b, m - 2, m)

def modDivide(a, b, m):
	a = a % m
	inv = modInverse(b, m)
	return inv * a % m

def char_position(letter):
	return ord(letter) - 97
for i in range(1, 501):
	factorial[i] = i * factorial[i - 1] % mod
for _ in range(int(input())):
	S = input()
	N = len(S)
	alphabet = [0] * 53
	for i in range(N):
		x = char_position(S[i].lower())
		if S[i].isupper():
			x += 26
		alphabet[x] += 1
	sol = factorial[N]
	for i in alphabet:
		if i > 1:
			sol = modDivide(sol, factorial[i], mod)
	print(sol)


import math as m
t = int(input())
for i in range(t):
	s = input()
	l = len(s)
	p = set(s)
	r = {j: s.count(j) for j in set(s)}
	d = 1
	for k in r.values():
		d *= m.factorial(k)
	print(m.factorial(l) // d % (10 ** 9 + 7))


from math import *
for u in range(int(input())):
	s = input()
	n = len(s)
	l = factorial(n)
	d = set(s)
	for i in d:
		l = l // factorial(s.count(i))
	print(l % (10 ** 9 + 7))


import collections
fact = [1] * 510
MOD = 10 ** 9 + 7
for i in range(2, 502):
	fact[i] = fact[i - 1] * i % MOD
for _ in range(int(input())):
	s = input()
	d = collections.Counter(s)
	n = len(s)
	num = fact[n]
	den = 1
	for i in d:
		den = den * fact[d[i]] % MOD
	inv = pow(den, MOD - 2, MOD)
	print(num * inv % MOD)


from collections import Counter
import math
mod = pow(10, 9) + 7
t = int(input())
for _ in range(t):
	s = input()
	p = 1
	count = dict(Counter(s))
	for i in count:
		p = p * math.factorial(count[i])
	x = math.factorial(len(s)) // p
	x = x % mod
	print(x)


def fact(N):
	c = 1
	if N == 0:
		return 1
	for i in range(1, N + 1):
		c *= i
	return c
from collections import Counter
for _ in range(int(input())):
	s = list(input())
	d = Counter(s)
	p = 10 ** 9 + 7
	m = 1
	for v in d.values():
		m *= fact(v)
	print(fact(len(s)) // m % p)


mod = 1000000007
read_int = lambda : int(input().strip())
read_str = lambda : input().strip()
read_str_arr = lambda : input().strip().split()
read_int_arr = lambda : [int(x) for x in input().strip().split()]
fact = [1] * 501
for i in range(2, 501):
	fact[i] = i * fact[i - 1] % mod

def solve():
	s = read_str()
	freq = {}
	for e in s:
		if e in freq:
			freq[e] += 1
		else:
			freq[e] = 1
	ans = fact[len(s)]
	for f in freq:
		inv = pow(fact[freq[f]], mod - 2, mod)
		ans = ans * inv % mod
	print(ans)
for _ in range(int(input())):
	solve()


def factorial(n):
	p = 1
	for i in range(n, 0, -1):
		p = p * i
	return p

def count(s):
	l4 = []
	l = []
	for i in range(len(s)):
		c = 0
		if s[i] not in l:
			for j in range(i, len(s)):
				if s[i] == s[j]:
					l.append(s[i])
					c += 1
			l4.append(c)
	return l4
t = int(input())
for x in range(t):
	s = input()
	l = len(s)
	k = count(s)
	pro = 1
	for i in range(len(k)):
		y = factorial(k[i])
		if y != 0:
			pro = pro * y
	print(factorial(l) // pro % (10 ** 9 + 7))


def fact(n):
	f = 1
	for i in range(1, n + 1):
		f = f * i
	return f

def main():
	t = int(input())
	for i in range(t):
		D = {}
		x = input()
		for j in x:
			if j in D:
				D[j] += 1
			else:
				D[j] = 1
		ans = fact(len(x))
		for j in D.values():
			if j > 1:
				ans = ans // fact(j)
		print(ans % 1000000007)
main()


import math
for _ in range(int(input())):
	s = input()
	a = [0] * 26
	b = [0] * 26
	for i in range(len(s)):
		if s[i].islower():
			a[97 - ord(s[i])] += 1
		else:
			b[65 - ord(s[i])] += 1
	sum = math.factorial(len(s))
	su = sum
	for i in range(26):
		su = su // (math.factorial(a[i]) * math.factorial(b[i]))
	print(su % (10 ** 9 + 7))


import math
mod = 1000000007
for i in range(int(input())):
	s = input()
	cnt = math.factorial(len(s))
	d = dict()
	for i in s:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	for i in d:
		cnt = cnt // math.factorial(d[i])
	print(cnt % mod)


from math import factorial
t = int(input())
for _ in range(t):
	line = input()
	char = []
	for i in line:
		char.append(i)
	char.sort()
	same = []
	current = char[0]
	k = 0
	for i in char:
		if i == current:
			k += 1
		else:
			current = i
			if k > 1:
				same.append(k)
			k = 1
	same.append(k)
	ans = factorial(len(char))
	for i in same:
		ans //= factorial(i)
	print(ans % 1000000007)


import math
t = int(input())
for i in range(t):
	s = input()
	st = set(s)
	l = []
	for j in st:
		l.append(s.count(j))
	f = math.factorial(len(s))
	r = 1
	for j in l:
		r = r * math.factorial(j)
	print(f // r % (10 ** 9 + 7))


import math
m = 7 + 10 ** 9
for z in range(int(input())):
	s = input()
	d = {}
	n = len(s)
	for x in s:
		if x not in d:
			d[x] = 0
		d[x] += 1
	f = 1
	for x in d.keys():
		f *= math.factorial(d[x])
	print(math.factorial(n) // f % m)


from math import *
T = int(input())
for i in range(T):
	st = input()
	d = {}
	for x in st:
		if x not in d:
			d[x] = 1
		else:
			d[x] += 1
	d1 = {}
	ans = factorial(len(st))
	for i in range(len(st)):
		if st[i] not in d1:
			ans //= factorial(d[st[i]])
			d1[st[i]] = 1
	ans %= 1000000007
	print(ans)


def main():
	from sys import stdin, stdout
	from math import factorial
	for _ in range(int(stdin.readline())):
		s = stdin.readline().strip()
		count = factorial(len(s))
		while len(s):
			count //= factorial(s.count(s[0]))
			s = s.replace(s[0], '')
		stdout.write(str(count % 1000000007) + '\n')
main()


import math
from math import *
t = int(input())
while t > 0:
	str = input()
	sum = 1
	list = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z']
	for i in list:
		sum = sum * math.factorial(str.count(i))
	z = math.factorial(len(str)) // sum
	print(z % 1000000007)
	t = t - 1


from collections import Counter
from math import factorial
for _ in range(int(input())):
	s = input()
	c = Counter(s)
	k = factorial(len(s))
	for value in c.values():
		if value > 1:
			k = k // factorial(value)
	print(k % (10 ** 9 + 7))


import math
t = int(input())
for i in range(t):
	s = input()
	A = [0] * 26
	B = [0] * 26
	for j in range(len(s)):
		if 65 <= ord(s[j]) <= 90:
			A[ord(s[j]) % 65] += 1
		elif 97 <= ord(s[j]) <= 122:
			B[ord(s[j]) % 97] += 1
	ans = math.factorial(len(s))
	for j in A:
		if j > 1:
			ans //= math.factorial(j)
	for j in B:
		if j > 1:
			ans //= math.factorial(j)
	while ans >= 1000000007:
		ans = ans % 1000000007
	print(ans)


fact = [1] * 505
mod = 10 ** 9 + 7
for i in range(1, 505):
	fact[i] = fact[i - 1] * (i + 1)
t = int(input())
for _ in range(0, t):
	s = input()
	n = len(s)
	mp = {}
	for ch in s:
		if ch in mp:
			mp[ch] += 1
		else:
			mp[ch] = 1
	ans = 1
	for p in mp:
		ans = ans * fact[mp[p] - 1]
	print(fact[n - 1] // ans % mod)


def fat(i):
	if i <= 1:
		return 1
	return i * fat(i - 1)
for _ in range(int(input())):
	s = input()
	l = len(s)
	nt = [0] * 52
	x = ord('a')
	y = ord('z')
	for i in s:
		z = ord(i)
		if z >= x and z <= y:
			nt[z - x] += 1
		else:
			nt[z - ord('A') + 26] += 1
	a = fat(l)
	for i in nt:
		a //= fat(i)
	print(a % 1000000007)


import math

def snek(string):
	l = list(string)
	u = list(set(l))
	c = []
	for i in range(len(u)):
		count = l.count(u[i])
		c.append(count)
	return c
t = int(input())
for i in range(t):
	n = input()
	c = snek(n)
	ans = math.factorial(len(n))
	d = 1
	for j in range(len(c)):
		d *= math.factorial(c[j])
	ans //= d
	print(ans % (10 ** 9 + 7))


from math import factorial
from collections import Counter
mod = 10 ** 9 + 7
facts = [1, 1]
for i in range(2, 1000):
	facts.append(facts[-1] * i)

def soln(s):
	counts = Counter(s)
	cur = facts[len(s)]
	div = 1
	for val in counts.values():
		div *= facts[val]
	return cur // div % mod
for _ in range(int(input())):
	s = input()
	print(soln(s))


from math import factorial
from collections import Counter
t = int(input())

def wordCount(s):
	a = set(s)
	d = Counter(s)
	n = len(s)
	x = factorial(n)
	for i in a:
		x //= factorial(d[i])
	return x
while t:
	t -= 1
	s = input()
	print(wordCount(s) % (10 ** 9 + 7))


def fac(m):
	ans = 1
	for i in range(1, m + 1):
		ans *= i
	return ans
T = int(input())
for _ in range(T):
	L = list(input())
	n = len(L)
	S = set(L)
	d = {}
	for i in S:
		d[i] = 0
	for i in range(len(L)):
		d[L[i]] += 1
	ans = fac(n)
	for i in d:
		ans //= fac(d[i])
	print(ans % (10 ** 9 + 7))


import collections
from math import factorial
m = 10 ** 9 + 7
for _ in range(int(input())):
	s = input()
	count = collections.Counter(s)
	y = factorial(len(s))
	x = 1
	for i in count.values():
		if i > 1:
			x *= factorial(i)
	print(y // x % m)


mod = 10 ** 9 + 7

def perm(n):
	ans = 1
	for i in range(1, n + 1):
		ans *= i
	return ans
for _ in range(int(input())):
	strli = list(input())
	n = len(strli)
	res = perm(n)
	setli = set(strli)
	for a in setli:
		cnt = strli.count(a)
		temp = perm(cnt)
		res //= temp
	print(res % mod)


from collections import Counter as Cn
from math import factorial as F
mod = 10 ** 9 + 7
for _ in range(int(input())):
	s = input()
	X = Cn(s)
	R = 1
	for i in X:
		R *= F(X[i] % mod) % mod
	print(F(len(s)) // R % mod)


MOD = 10 ** 9 + 7
p = 10 ** 3 + 3
fact = [1] * p
for i in range(1, p):
	fact[i] = fact[i - 1] * i % MOD

def MI(a, m):
	return pow(a, m - 2, m)
from collections import Counter
for _ in range(int(input())):
	s = input()
	n = len(s)
	c = Counter(s)
	ans = fact[n]
	for i in c:
		if c[i] >= 1:
			ans = ans * MI(fact[c[i]], MOD) % MOD
	print(ans % MOD)


from collections import Counter
import math
tc = int(input())
while tc > 0:
	s = input()
	k = math.factorial(s.__len__())
	x = Counter(s)
	for val in x.values():
		if val > 1:
			k = k // math.factorial(val)
	k = int(k)
	k = k % (10 ** 9 + 7)
	print(k)
	tc -= 1


import math
n = int(input())
MOD = pow(10, 9) + 7
while n != 0:
	s = input()
	a = [0 for i in range(26)]
	A = [0 for i in range(26)]
	for i in s:
		if i >= 'a' and i <= 'z':
			a[ord(i) - 97] += 1
		else:
			A[ord(i) - 65] += 1
	N = math.factorial(len(s))
	for i in range(26):
		N = N // math.factorial(a[i])
		N = N // math.factorial(A[i])
	print(N % MOD)
	n -= 1


def main():
	from sys import stdin, stdout
	from math import factorial
	t = int(stdin.readline())
	while t:
		s = stdin.readline().strip()
		dic = {}
		for ele in s:
			if ele in dic.keys():
				dic[ele] += 1
			else:
				dic[ele] = 1
		a = factorial(len(s))
		for key in dic.keys():
			a //= factorial(dic[key])
		stdout.write(str(a % 1000000007) + '\n')
		t -= 1
main()


import math
m = 10 ** 9 + 7
for t in range(int(input())):
	s = input()
	l = len(s)
	h = []
	for i in range(256):
		h.append(0)
	for i in range(l):
		h[ord(s[i])] += 1
	ans = 1
	for i in range(256):
		ans *= math.factorial(h[i])
	x = math.factorial(l)
	x = x // ans
	print(x % m)


def integer_list():
	return list(map(int, input().split()))

def string_list():
	return list(map(str, input().split()))

def hetro_list():
	return list(input().split())
import math
from collections import Counter
maxn = 502
fact = [0] * maxn
ifact = [0] * maxn
fact[0] = 1
ifact[0] = 1
mod = 10 ** 9 + 7
for i in range(1, maxn):
	fact[i] = fact[i - 1] * i % mod
	ifact[i] = ifact[i - 1] * pow(i, mod - 2, mod) % mod

def main():
	pass
t = int(input())
for _ in range(t):
	s = input()
	dct = Counter(s)
	ans = fact[len(s)]
	for ele in dct:
		ans *= ifact[dct[ele]]
		ans %= mod
	print(ans)


def factorial(n):
	f = 1
	for i in range(1, n + 1):
		f = f * i
	return f
t = int(input())
for j in range(0, t):
	s = input()
	d = {}
	for i in s:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	a = factorial(len(s))
	b = 1
	for k in d:
		if d[k] > 1:
			b = b * factorial(d[k])
	print(a // b % 1000000007)


from collections import Counter
from operator import mul
from functools import reduce
from math import factorial

def Main():
	T = int(input())
	for n in range(T):
		S = input()
		print(factorial(len(S)) // reduce(mul, [factorial(i) for i in Counter(S).values()]) % (10 ** 9 + 7))
Main()


from collections import Counter
from math import factorial
num = 10 ** 9 + 7
for _ in range(int(input())):
	string = input()
	count = Counter(string)
	f = factorial(len(string))
	x = 1
	for i in count.values():
		if i > 1:
			x *= factorial(i)
	print(f // x % num)


import sys
import math
from time import time
from itertools import permutations, combinations
import collections
import functools
from fractions import gcd, Fraction
import string
import operator
import bisect

class timed(object):

	def __init__(self, func):
		self.func = func

	def __call__(self, *args):
		t1 = time()
		ret = self.func(*args)
		dif_time = time() - t1
		print('%s: returned %s in %f seconds' % (self.func.__name__, ret, dif_time))
		return ret

def comp(f1, f2, *args):
	t1 = time()
	r1 = f1(*args) if f1 is not None else None
	t2 = time()
	r2 = f2(*args) if f2 is not None else None
	t3 = time()
	res = '%5s: %s in %f\n%5s: %s in %f' % (f1.__name__ if f1 is not None else None, r1, t2 - t1, f2.__name__ if f2 is not None else None, r2, t3 - t2)
	if r1 != r2:
		dr = '!! DIFFERENT RESULTS !!'
		res = dr + '\n' + res + '\n' + dr
	print(res)
	return r1 if r1 == r2 else None
MODULO = 1000000007

def choose(n, k):
	if 0 <= k <= n:
		ntok = 1
		ktok = 1
		for t in range(1, min(k, n - k) + 1):
			ntok *= n
			ktok *= t
			n -= 1
		return ntok // ktok
	else:
		return 0

def alg(s):
	counts = [(a, s.count(a)) for a in set(s)]
	res = 1
	remaining_spots = len(s)
	for (ch, nb) in counts:
		res *= choose(remaining_spots, nb)
		res %= MODULO
		remaining_spots -= nb
	return res

def main():
	data = sys.stdin
	nb = int(data.readline())
	for icase in range(nb):
		s = data.readline().strip()
		res = alg(s)
		print(res)
main()


import math

def count(s):
	d = {}
	k = set(s)
	for y in k:
		d[y] = 0
	for y in s:
		d[y] += 1
	ans = math.factorial(len(s))
	for y in d.keys():
		ans = ans // math.factorial(d[y])
	return int(ans) % (10 ** 9 + 7)
test_cases = int(input())
while test_cases != 0:
	data = input()
	print(count(data))
	test_cases -= 1


from math import factorial

def ans(s):
	l = list(s)
	a = list(set(l))
	z = [factorial(l.count(x)) for x in a if l.count(x) > 1]
	mul = 1
	for i in range(len(z)):
		mul = mul * z[i]
	return mul
for i in range(int(input())):
	s = input()
	x = ans(s)
	print(factorial(len(s)) // x % 1000000007)