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

```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 = '#pradeep singh NIT trichy\n#pradeepsng30@yahoo.com\n\np=1000000007\nmod=p;\n\ndef fact(n):\n\tf=1\n\ti=2\n\twhile (i<=n):\n\t\tf=f*i\n\t\tf=f%mod\n\t\ti=i+1\n\treturn f\n\t\t\n\ndef perm_count(orig_list, k):\n\n\tmaster_list  = []\n\tmaster_list.append(list(orig_list))\n\twhile k > 0:\n\t    big_list = list(master_list) \n\t    for each_list in big_list: \n\t        for each_temp_list in permuter(each_list):\n\t            if each_temp_list not in master_list:\n\t                master_list.append(each_temp_list)\n\t                \n\t\n\t    k-=1\n\t\n\ttotal_count = len(master_list)\n#\tprint sorted(master_list) #If you need a sanity check, feel free to leave out\n\treturn total_count\n\t#end perm_count\n\ndef permuter(my_list):#returns a list of lists\n    lists_list = []\n   \n    for i in range(len(my_list)):\n        for j in range(len(my_list)):\n            temp_list = my_list[:]\n            if i != j:\n                temp_list[i],temp_list[j] = temp_list[j],temp_list[i]\n            if temp_list not in lists_list:\n                lists_list.append(list(temp_list))\n\n    return lists_list\n\n\n\n\ndef modInv(x):\n\ty = pow(x, p-2, p)\n\treturn y\n\t\n\n\ndef numP(wordArray):\n\n\tletterOccurances = list()\n# List of letters that have been counted in wordArray\n\tcountedLetters = list()\n\t\n\twordLength = len(wordArray)\n\t\n\tnumerator = fact(wordLength)%mod\n\t\n# Loops through wordArray, counts how many times a letter occurs, skips over\n# already counted letters using a list of such letters (list updated each time) \n\tfor letter in wordArray:\n\t    if letter in countedLetters:\n\t        continue\n\t    letterOccurances.append(wordArray.count(letter))\n\t    countedLetters.append(letter)\n\t\n\t# Denominator of final formula\n\tdenominator = 1\n\tANS=1\n\tANS=numerator\n#\tmodInv(900)\n#\tprint "here"\n\tfor i in letterOccurances:\n\t\tANS=ANS*modInv(fact(i))%mod\n\t    #denominator = (denominator * math.factorial(i))\n\t\n\treturn ANS\t\n    \t\n    \t\n    \n    \n    \ndef ans(a):\n#\tprint "here"\n\tif(len(a)<4):\n\t\treturn 0\n#\treturn 0\n\tmylist=list(a)\n\tn=numP(mylist)\n#\tn=24\n\tm=perm_count(mylist,2)%mod\n\treturn (n*(n-m))%mod\n\t\n\n\nt = int(input())\n#print t\n\nwhile (t>0):\n\ta=input()\n#\tprint a\n\tprint(ans(a))\n\t#print "\\n"\n\tt=t-1\n#print perm_count(D,2)'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13807