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.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = '# your code goes here\nfrom collections import defaultdict\n\n\ndef fac(num, modulo):\n ans = 1\n for i in range(2, num+1):\n  ans = (ans*i)%modulo\n return ans\n \n \ndef fast_expo(num, p, modulo):\n num %= modulo\n exxp = 1\n while(p>0):\n  if p&1:\n   exxp = exxp * num%modulo\n  num = num * num % modulo\n  p >>= 1\n return exxp\n \n\nmodulo = 1000000007\n\nt = int(input())\n\nfor i in range(t):\n s = input().strip()\n \n mp = defaultdict(int)\n for si in s:\n  mp[si] += 1\n  \n denom = 1\n for alpha in mp.keys():\n  denom = denom*fac(mp[alpha], modulo)\n denom = fast_expo(denom, modulo-2, modulo)\n \n nfac = fac(len(s), modulo)\n nfac = nfac*denom%modulo\n  \n print(int(nfac))'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 14005