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

Starter code:

Solutions:
# cook your dish here
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))

# cook your dish here
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 list(c.values()):
  
  if value>1:
   k=k//factorial(value)
   
 print(k%(10**9+7))
 
 
 


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

# cook your dish here
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 list(c.values()):
  
  if value>1:
   k=k//factorial(value)
   
 print(k%(10**9+7))
 
 
 


# cook your dish here
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)
 
 


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)

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)

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 list(dic.keys()):
   dic[p] += 1
  else:
   dic[p] = 1
 f = fact(N)
 for t in list(dic.keys()):
  f = f // fact(dic[t])
 print(f % mod)


import math
t=int(input())
#print(math.factorial(5))
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))

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)


# cook your dish here
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)) 

# your code goes here
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))

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 list(d.values()):
  y= fact(i)
  y = pow(y,e-2,e)
  x=(x*y)%e
 print(x)


# your code goes here
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)

# cook your dish here
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)




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