This follows from Game of Thrones - I.

Now that the king knows how to find out whether a given word has an anagram which is a palindrome or not, he encounters another challenge. He realizes that there can be more than one palindrome anagrams for a given word. Can you help him find out how many palindrome anagrams are possible for a given word ?

The king has many words. For each given word, he needs to find out the number of palindrome anagrams of the string. As the number of anagrams can be large, the king needs the number of anagrams % (10^{9}+ 7).

Input format :

A single line which contains the input string

Output format : 

A single line which contains the number of anagram strings which are palindrome % (10^{9} + 7).

Constraints : 

1<=length of string <= 10^5 

Each character of the string is a lowercase alphabet. 

Each test case has at least 1 anagram which is a palindrome. 

Sample Input 01 :

aaabbbb

Sample Output 01 :

3 

Explanation : 

Three palindrome permutations of the given string are abbabba , bbaaabb and bababab.

Sample Input 02 :

cdcdcdcdeeeef

Sample Output 02 :

90

Difficulty: MEDIUM_HARD
Tags: Combinatorics

Starter code:

Solutions:
def fact_mod_p_brute(n, p):
	if n == 0:
		return 1
	res = 1
	for i in range(1, n + 1):
		res *= i
		res = res % p
	return res
s2 = [0 for i in range(270)]
s = str(input())
for l in s:
	s2[ord(l)] += 1
c = 0
sum = 0
for i in range(270):
	if s2[i] % 2 == 1:
		c += 1
	s2[i] //= 2
	sum += s2[i]
pp = 1000000007
if c > 1:
	print('0')
else:
	licz = fact_mod_p_brute(sum, pp)
	mian = 1
	for i in range(270):
		mian *= fact_mod_p_brute(s2[i], pp)
		mian = mian % pp
	print(licz * pow(mian, pp - 2, pp) % pp)


x = input()
char = list(x)
l = len(char)
count = 0
num = [ord(char[i]) for i in range(0, l)]
fact = 1
div = 1
num.sort()
if l > 1:
	for i in range(1, l // 2 + 1):
		fact = fact * i
	i = 0
	j = 0
	while i < l:
		count = 0
		while j < l and num[i] == num[j]:
			count += 1
			j += 1
		i = j
		if count > 1:
			div = 1
			d = int(count // 2)
			for i in range(1, d + 1):
				div = div * i
			fact = fact // div
print(fact % 1000000007)


import collections, math, sys
s = sys.stdin.readline().strip()
c = collections.Counter(s)
n = math.factorial(sum((v // 2 for v in c.values())))
for v in c.values():
	n //= math.factorial(v // 2)
print(n % 1000000007)


def c(n, k):
	if k > n - k:
		k = n - k
	r = 1
	for i in range(k):
		r = r * (n - i) // (i + 1)
	return r

def m(k):
	r = 1
	for i in range(len(k)):
		r *= c(sum(k[:i + 1]), k[i])
	return r % (10 ** 9 + 7)
word = input()
counts = {}
for x in word:
	if x not in counts:
		counts[x] = 0
	counts[x] += 1
for x in counts.keys():
	counts[x] //= 2
print(m(list(counts.values())))


from math import factorial as fac
from collections import Counter

def main():
	s = input()
	c = Counter(s)
	ns = [x // 2 for x in c.values() if x % 2 == 0]
	length = len(s)
	half = length // 2
	pos = fac(half)
	for i in ns:
		pos = pos // fac(i)
	print(pos % (10 ** 9 + 7))
main()


import sys

def main():
	text = sys.stdin.readline()
	text = text.strip()
	dictnum = {}
	for ch in text:
		if ch in dictnum:
			dictnum[ch] += 1
		else:
			dictnum[ch] = 1
	calcresult = 1
	length = len(text)
	length //= 2
	for i in range(2, length + 1):
		calcresult *= i
	nums = []
	for value in dictnum.values():
		value //= 2
		if value >= 2:
			nums.extend([i for i in range(2, value + 1)])
	if len(nums) > 0:
		v2 = 1
		for value in nums:
			v2 *= value
		calcresult //= v2
	calcresult %= 1000000007
	sys.stdout.write(str(calcresult) + '\n')
main()


from collections import Counter
from math import factorial
BIGNUM = 10 ** 9 + 7

def count_palindrome_anagrams(line):
	letters = Counter(line)
	ret = factorial(len(line) // 2)
	for frequency in letters.values():
		ret //= factorial(frequency // 2)
	return ret % BIGNUM
line = input()
print(count_palindrome_anagrams(line))


def primelist(A):
	d = {}
	for i in range(2, A + 1):
		d[i] = 0
	for i in range(2, A):
		for j in range(2, int(A ** 0.5) + 2):
			if i * j <= A:
				d[i * j] = 1
	return sorted([i for i in d if d[i] == 0])

def noMult(m, A):
	(tmp, rt) = (m, 0)
	while tmp <= A:
		rt += A // tmp
		tmp *= m
	return rt

def perm(A):
	t = sum(A)
	primel = primelist(t)
	d = {}
	for i in primel:
		d[i] = noMult(i, t)
	for i in A:
		for j in primel:
			if j > i:
				break
			d[j] -= noMult(j, i)
	rt = 1
	for i in d:
		rt = rt * i ** d[i] % (10 ** 9 + 7)
	return rt

def noPerm(A):
	d = {}
	for i in A:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	tmp = []
	for i in d:
		tmp.append(d[i] // 2)
	return perm(tmp)
print(noPerm(input().strip()))


string = input()
l = []
m = []
for c in string:
	n = 0
	if c in m:
		continue
	for i in range(0, len(string)):
		if string[i] == c:
			n = n + 1
	m.append(c)
	l.append(n)
p = [j // 2 for j in l]

def fact(x):
	if x == 0:
		return 1
	else:
		i = 1
		prod = 1
		while i <= x:
			prod = prod * i
			i = i + 1
		return prod
ans = fact(len(string) // 2)
for i in p:
	ans = ans // fact(i)
print(ans % (10 ** 9 + 7))


import math
chars = list(input())
n = math.factorial(len(chars) // 2)
for i in range(ord('a'), ord('z') + 1):
	n //= math.factorial(chars.count(chr(i)) // 2)
print(n % 1000000007)


import math
cList = list(input())
ucList = set(cList)
letCount = []
Norm = 1
result = 0
for letter in ucList:
	if cList.count(letter) % 2 == 0:
		letCount.append(cList.count(letter) // 2)
	elif cList.count(letter) > 2:
		letCount.append((cList.count(letter) - 1) // 2)
for letter in letCount:
	result += letter
	Norm = Norm * math.factorial(letter)
print(math.factorial(result) // Norm % (10 ** 9 + 7))


import sys
import array
import math

def fact(x):
	if not hasattr(fact, 'old'):
		fact.old = {1: 1}
	_min = -1
	for k in fact.old.keys():
		if abs(x - k) < _min or _min == -1:
			_min = abs(x - k)
			_argmin = k
	val = fact.old[_argmin]
	while _argmin > x:
		val = val // _argmin
		_argmin -= 1
	while _argmin < x:
		_argmin += 1
		val = val * _argmin
	fact.old[x] = val
	return val
str = sys.stdin.readline()
count = [0] * 26
modulus = pow(10, 9) + 7
for c in str[:-1]:
	count[ord(c) - ord('a')] += 1
one = 0
for i in range(len(count)):
	if count[i] % 2 != 0:
		one += 1
		count[i] -= 1
if one > 1:
	print('0')
else:
	total = 0
	for i in range(len(count)):
		count[i] = count[i] // 2
		total += count[i]
	bot = 1
	for i in count:
		bot = bot * fact(i)
	top = fact(total)
	print(top // bot % (pow(10, 9) + 7))


from collections import defaultdict

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

def has_palindromic_anagram(string_):
	counts = defaultdict(lambda : 0)
	for char in string_:
		counts[char] += 1
	n_odd_counts = len([c for c in counts.values() if c % 2 != 0])
	return n_odd_counts <= 1

def count_palindromic_anagrams(string_):
	if not has_palindromic_anagram(string_):
		return 0
	counts = defaultdict(lambda : 0)
	for char in string_:
		counts[char] += 1
	nums = [x // 2 for x in counts.values() if x > 1]
	result = 1
	for i in range(sum(nums), max(nums), -1):
		result *= i
	nums.remove(max(nums))
	for num in nums:
		result //= factorial(num)
	return result

def main():
	string_ = input()
	n = count_palindromic_anagrams(string_)
	print(n % (10 ** 9 + 7))
main()


import collections
import sys
import math
import fractions

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m):
	(g, x, y) = egcd(a, m)
	if g != 1:
		return None
	else:
		return x % m
chars = list(sys.stdin.readline().rstrip('\n'))
cnt = collections.Counter(chars)
hl = len(chars) // 2
for c in cnt.keys():
	cnt[c] //= 2
bden = max(cnt.values())
for k in cnt.keys():
	if cnt[k] == bden:
		del cnt[k]
		break
denom = collections.Counter()
for v in cnt.values():
	denom.update(range(2, v + 1))
result = 1
for n in range(hl, bden, -1):
	result = result * n % (10 ** 9 + 7)
for d in list(denom.keys()):
	inv = modinv(d, 10 ** 9 + 7)
	for i in range(denom[d]):
		result = result * inv % (10 ** 9 + 7)
print(int(result % (10 ** 9 + 7)))


import sys
import math
import collections
import functools
import operator
code = sys.stdin.read().strip()
print(math.factorial(len(code) // 2) // functools.reduce(operator.mul, [math.factorial(i // 2) for i in collections.Counter(code).values()], 1) % (10 ** 9 + 7))


import collections
import math

def check_palindrome(word):
	checked = set()
	already_odd = False
	for c in word:
		if c not in checked:
			if word.count(c) % 2:
				if already_odd:
					return False
				already_odd = True
			checked.add(c)
	return True
string = input()
if check_palindrome(string):
	counter = collections.Counter(string)
	zähler = 0
	nenner = 1
	for char in counter:
		zähler += math.floor(counter[char] / 2)
		nenner *= math.factorial(math.floor(counter[char] / 2))
	print(math.factorial(zähler) // nenner % 1000000007)
else:
	print(0)


from collections import defaultdict
import math

def gameofthrones_2(letters):
	frequencies = defaultdict(int)
	for letter in letters:
		frequencies[letter] += 1
	half_freq = defaultdict(int)
	n = 1000000007
	prods = 1
	halflen = 0
	for (letter, count) in frequencies.items():
		if count % 2 != 0:
			count -= 1
		prod = math.factorial(int(count / 2))
		prods *= prod
		prods = prods
		half_freq[letter] += int(count / 2)
		halflen += int(count / 2)
	result = math.factorial(halflen) % n
	prods = pow(prods, n - 2, n)
	result = result * prods
	result = result % n
	return int(result)
print(gameofthrones_2(input()))


from math import factorial, floor
d = {'a': 0, 'b': 0, 'c': 0, 'd': 0, 'e': 0, 'f': 0, 'g': 0, 'h': 0, 'i': 0, 'j': 0, 'k': 0, 'l': 0, 'm': 0, 'n': 0, 'o': 0, 'p': 0, 'q': 0, 'r': 0, 's': 0, 't': 0, 'u': 0, 'v': 0, 'w': 0, 'x': 0, 'y': 0, 'z': 0}
string = input()
s = len(string) // 2
for i in string:
	d[i] = d[i] + 1
fact = factorial(s)
keys = d.keys()
for i in keys:
	fact = fact // factorial(d[i] // 2)
print(fact % (10 ** 9 + 7))


from fractions import Fraction
c = [0] * 26
s = input()
n = len(s) // 2
for i in s:
	c[ord(i) - ord('a')] += 1
da = []
for i in range(26):
	c[i] //= 2
	if c[i] > 0:
		for j in range(1, c[i] + 1):
			da.append(j)
val = Fraction(1, 1)
for i in range(n):
	val *= Fraction(i + 1, da[i])
print(val.numerator % (10 ** 9 + 7))


import math
prime = 1000000007

def choose(result, n, r):
	k = min(r, n - r)
	numerator = result
	denominator = 1
	n = n - (k - 1)
	for i in range(k):
		numerator *= n
		n += 1
		if numerator > prime:
			numerator %= prime
		denominator *= k
		k -= 1
		if denominator > prime:
			denominator %= prime
	return numerator * modInverse(denominator, prime) % prime

def modInverse(b, n):
	return pow(b, n - 2, n)
word = input()
table = {}
ln = len(word)
result = 1
for i in range(ln):
	if word[i] in table:
		table[word[i]] = table[word[i]] + 1
	else:
		table[word[i]] = 1
n = math.floor(ln / 2)
for key in table:
	r = math.floor(table[key] / 2)
	result = choose(result, n, r)
	if result > prime:
		result %= prime
	n -= r
print(result)


zz = input()
mod = 1000000007
arr = [0] * 26
for i in zz:
	arr[ord(i) - 97] += 1
l = len(zz)
lfinal = int(l / 2)
den = 1
for i in range(0, 26):
	if arr[i] % 2 != 0:
		arr[i] -= 1
	arr[i] /= 2
	fact = 1
	for j in range(1, int(arr[i] + 1)):
		fact = fact * j % mod
	den = den * fact % mod
num = 1
for i in range(1, lfinal + 1):
	num = num * i % mod
deninv = pow(den, mod - 2, mod)
result = num * deninv % mod
print(result)


import sys
MOD = 10 ** 9 + 7

def fact(n):
	if n <= 0:
		return 1
	result = 1
	for i in range(1, n + 1):
		result *= i
	return result
chars = sys.stdin.readline().strip()
(n_odds, n_evens) = (0, 0)
c_count = {}
for char in chars:
	if char not in c_count:
		c_count[char] = 0
	c_count[char] += 1
for (char, count) in c_count.items():
	if count % 2 != 0:
		n_odds += 1
		n_evens += count - 1
	else:
		n_evens += count
if n_odds > 1:
	print('0')
	sys.exit(0)
n_evens //= 2
total_perm = fact(n_evens)
for (char, count) in c_count.items():
	if count % 2 != 0:
		count -= 1
	count //= 2
	total_perm //= fact(count)
print(total_perm % MOD)


import collections, math, sys
s = sys.stdin.readline().strip()
c = collections.Counter(s)
n = math.factorial(sum((v // 2 for v in c.values())))
for v in c.values():
	if v > 1:
		n //= math.factorial(v // 2)
print(n % 1000000007)


from math import factorial

def func(st):
	ar = sorted(list(st))
	s = 1
	odd_flag = 0
	sp = 0
	rt = factorial(len(st) // 2)
	while s < len(ar):
		if ar[s - 1] != ar[s]:
			rt //= factorial((s - 1 - sp + 1) // 2)
			sp = s
		s += 1
	rt //= factorial((s - 1 - sp + 1) // 2)
	return rt % 1000000007
print(func(input()))


MOD = 1000000007

def main():
	s = input()
	cnt = [0] * 26
	for ch in s:
		cnt[ord(ch) - ord('a')] += 1
	n = len(s)
	size = n // 2
	invfact = [1] * size
	for i in range(2, size):
		invfact[i] = invfact[i - 1] * pow(i, MOD - 2, MOD) % MOD
	ans = 1
	for i in range(2, n // 2 + 1):
		ans = ans * i % MOD
	for x in cnt:
		ans = ans * invfact[x // 2] % MOD
	print(ans)
main()


givenString = input()
strLen = len(givenString) // 2
letterHash = {}
modPart = 1000000007
numerator = 1
denominator = 1
res = 1
for letter in givenString:
	val = letterHash.get(letter, None)
	if val is None:
		val = 0
	val += 1
	letterHash[letter] = val
for ii in range(1, strLen + 1):
	numerator = numerator * ii % modPart
res = numerator
for value in letterHash.values():
	for ii in range(1, value // 2 + 1):
		denominator = denominator * ii % modPart
print(numerator * pow(denominator, modPart - 2, modPart) % modPart)


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

def main():
	string = Counter(sys.stdin.readline().strip())
	string = {k: v // 2 for (k, v) in string.items() if v != 1}
	possibles = factorial(sum([v for v in string.values()]))
	duplicates = reduce(mul, [factorial(v) for v in string.values()])
	print(possibles // duplicates % int(1000000000.0 + 7))
main()


import collections, math, sys
s = sys.stdin.readline().strip()
c = collections.Counter(s)
n = math.factorial(sum((v // 2 for v in c.values())))
for v in c.values():
	if v > 1:
		n //= math.factorial(v // 2)
print(n % 1000000007)


import math

def getNumAnag(strDict):
	num = 0
	denom = []
	for i in strDict:
		num += strDict[i]
		if strDict[i] != 0:
			denom.append(strDict[i])
	numFact = math.factorial(num)
	denomFact = 1
	for i in range(len(denom)):
		denomFact *= math.factorial(denom[i])
	result = numFact // denomFact
	result %= 1000000000 + 7
	return result

def genFreqMap(s):
	strDict = {}
	for i in range(len(s)):
		if s[i] in strDict:
			strDict[s[i]] += 1
		else:
			strDict[s[i]] = 1
	for key in strDict:
		if strDict[key] % 2:
			strDict[key] = int((strDict[key] - 1) / 2)
		else:
			strDict[key] = int(strDict[key] / 2)
	return strDict
string = input()
strDict = genFreqMap(string)
anagrams = getNumAnag(strDict)
print(anagrams)


import math
s = input()
p = [0] * 26
for ch in s:
	p[ord(ch) - ord('a')] += 1
total = 0
divisor = 1
for i in range(26):
	p[i] = p[i] // 2
	total += p[i]
	divisor = divisor * math.factorial(p[i])
print(math.factorial(total) // divisor % 1000000007)


import math
bad = False
flag = False
s = input().strip()
ch = set(s)
ct = []
for x in ch:
	freq = s.count(x)
	if freq % 2 != 0 and flag:
		bad = True
		break
	elif freq % 2 != 0:
		flag = True
		if freq > 1:
			ct.append((freq - 1) // 2)
	else:
		ct.append(freq // 2)
n = len(s)
if not bad:
	p = 1
	for j in ct:
		p *= math.factorial(j)
	print(math.factorial(n // 2) // p % (10 ** 9 + 7))


from math import factorial

def multiset_permutation(string):
	palichars = ''.join((c * (string.count(c) // 2) for c in set(string)))
	mset = [palichars.count(c) for c in set(palichars)]
	c = 1
	for m in mset:
		c = c * factorial(m)
	return factorial(len(palichars)) // c % (10 ** 9 + 7)
data = str(input().strip())
print(multiset_permutation(data))


import operator
import math
import functools

def count_palindromes(S):
	if len(S) % 2:
		for x in set(S):
			if S.count(x) % 2:
				S = S.replace(x, '', 1)
				break
	multiset = [S.count(x) // 2 for x in set(S)]
	M = 1
	for m in multiset:
		M *= math.factorial(m)
	return math.factorial(len(S) // 2) // M
S = str(input().strip())
print(count_palindromes(S) % (10 ** 9 + 7))


def factorial(n):
	ret = 1
	for i in range(2, n + 1):
		ret *= i
	return ret
s = str(input())
count = {}.fromkeys(set(s), 0)
for x in s:
	count[x] += 1
tmp = []
for x in count:
	if count[x] != 1:
		tmp.append(count[x] // 2)
ret = factorial(sum(tmp))
for d in tmp:
	ret //= factorial(d)
print(ret % (10 ** 9 + 7))


MOD = 10 ** 9 + 7
s = input()
C = {}
for c in s:
	C[c] = C.get(c, 0) + 1

def fact(n, MOD):
	f = 1
	for x in range(1, n + 1):
		f = f * x % MOD
	return f
n = 1
for c in C:
	n *= fact(C[c] >> 1, MOD)

def gcde(a, b):
	(r, u, v, r2, u2, v2) = (a, 1, 0, b, 0, 1)
	while r2 > 0:
		q = r // r2
		(r, u, v, r2, u2, v2) = (r2, u2, v2, r - q * r2, u - q * u2, v - q * v2)
	return (r, u, v)
(r, u, v) = gcde(n, MOD)
print(fact(len(s) >> 1, MOD) * u % MOD)


from math import factorial
string = str(input())
lis = []
intlis = []
for i in range(len(string)):
	lis.append(string[i])
lis.sort()
i = 0
count = 0
size = len(lis)
while i < size:
	count = lis.count(lis[i])
	intlis.append(count)
	i = i + count
total = 0
odd = 0
duplicates = 1
size = len(intlis)
for x in range(0, size):
	if intlis[x] % 2 == 0:
		total = total + intlis[x] / 2
		duplicates = duplicates * factorial(intlis[x] / 2)
	elif intlis[x] % 2 == 1 and odd == 0:
		odd = intlis[x]
		total = total + (intlis[x] - 1) / 2
		if odd > 1:
			duplicates = duplicates * factorial((intlis[x] - 1) / 2)
	else:
		print(0)
print(factorial(total) // duplicates % (10 ** 9 + 7))


import itertools
import math, sys
s = input()
count = 0
a = set(s)
dir = {}
flag = True
for i in a:
	count = s.count(i)
	dir[i] = count
vals = list(dir.values())
count = 0
for i in vals:
	if i % 2 == 1:
		count += 1
	if count == 2:
		sys.exit(0)
mul = 1
for i in dir:
	dir[i] = dir[i] // 2
	mul = mul * math.factorial(dir[i])
act = math.factorial(len(s) // 2) // mul
print(act % (10 ** 9 + 7))


import math

def count_panagrams(test_string):
	char_dict = {}
	for c in test_string:
		if c in char_dict:
			char_dict[c] += 1
		else:
			char_dict[c] = 1
	letters_permutations = 1
	mod_val = 10 ** 9 + 7
	for c in char_dict:
		if char_dict[c] == 1:
			continue
		if char_dict[c] % 2 != 0:
			letter_count = int((char_dict[c] - 1) / 2)
		else:
			letter_count = int(char_dict[c] / 2)
		letter_permutation = math.factorial(letter_count)
		letters_permutations = letter_permutation * letters_permutations
	permutations = math.factorial(int(len(test_string) / 2))
	permutations //= letters_permutations
	permutations %= mod_val
	return permutations
test_string = input().strip()
how_many = count_panagrams(test_string)
print(how_many)


from math import factorial
from functools import reduce
from collections import Counter
mod = 10 ** 9 + 7

def count_palindromes(s):
	chars_freq = [v // 2 for (k, v) in Counter(s).items()]
	return factorial(sum(chars_freq)) // reduce(lambda x, y: x * y, map(factorial, chars_freq)) % mod
s = input()
print(count_palindromes(s))


import math
word = input()
counts = {}
for letter in word:
	if letter not in counts.keys():
		counts[letter] = 1
	else:
		counts[letter] += 1
odds = 0
even_pairs = []
for count in counts.values():
	if count % 2 == 1:
		odds += 1
		even_pairs.append((count - 1) / 2)
	else:
		even_pairs.append(count / 2)
if len(word) % 2 != odds:
	print(0)
else:
	num_pals = math.factorial(sum(even_pairs))
	for letter_set in even_pairs:
		num_pals = num_pals // math.factorial(letter_set)
	print(num_pals % int(math.pow(10, 9) + 7))


import math
a = input()
a = ''.join(sorted(a))
chars = list(set(a))
chars.sort()
lens = [a.count(i) for i in chars]
odds = 0
for i in lens:
	if i % 2 == 1:
		odds += 1
if odds > 1 or (odds == 1 and len(a) % 2 == 0):
	print(0)
else:
	lens = [int(i / 2) for i in lens]
	tot = math.factorial(sum(lens))
	for i in lens:
		tot = tot // math.factorial(i)
	print(tot % (10 ** 9 + 7))


mod = 1000000007

def fact(n):
	a = 1
	for i in range(1, n + 1):
		a = a * i
	return a
s = input('')
l = len(s)
d = {}
for i in s:
	if i in d:
		d[i] = d[i] + 1
	else:
		d[i] = 1
n = l // 2
den = 1
for i in d:
	den = den * fact(d[i] // 2)
num = fact(n)
ans = num // den
ans = ans % mod
print(ans)


import collections, math, sys
s = sys.stdin.readline().strip()
c = collections.Counter(s)
n = math.factorial(sum((v // 2 for v in c.values())))
for v in c.values():
	if v > 1:
		n //= math.factorial(v // 2)
print(n % 1000000007)


def fac(n):
	if n == 0:
		return 1
	res = 1
	for i in range(1, n + 1):
		res *= i
	return res

def prod(iterable):
	p = 1
	for e in iterable:
		p *= e
	return p

def solve(s):
	d = {}
	for c in s:
		if not c in d:
			d[c] = 1
		else:
			d[c] += 1
	if len(s) % 2 == 1:
		for (k, v) in d.items():
			if v % 2 == 1:
				d[k] -= 1
				if d[k] == 0:
					del d[k]
				break
		else:
			return 0
	dups = []
	total = 0
	for (k, v) in d.items():
		if v % 2 == 1:
			return 0
		d[k] = v // 2
		dups.append(d[k])
		total += d[k]
	return fac(total) // prod(map(fac, dups)) % (10 ** 9 + 7)
s = input().strip()
print(solve(s))


import collections, math, sys
s = sys.stdin.readline().strip()
c = collections.Counter(s)
n = math.factorial(sum((v // 2 for v in c.values())))
for v in c.values():
	if v > 1:
		n //= math.factorial(v // 2)
print(n % 1000000007)


import collections
from math import factorial
s = input()
N = len(s)
letter_count = dict(collections.Counter(s))
for (letter, count) in letter_count.items():
	if count % 2 == 1:
		N -= 1
		if letter_count[letter] == 1:
			del letter_count[letter]
		else:
			letter_count[letter] -= 1
		break
result = factorial(N // 2)
f = 1
for i in letter_count.values():
	f = f * factorial(i // 2)
result = result // f
print(result % (10 ** 9 + 7))


from math import factorial
w = list(input())
c = [w.count(i) // 2 for i in set(w)]
l = len(w) // 2
ans = factorial(l)
for i in c:
	ans //= factorial(i)
print(int(ans) % 1000000007)


from math import factorial

def comb(n, k):
	return factorial(n) // factorial(n - k) // factorial(k)
line = input()
dct = {}
for ch in line:
	if ch in dct:
		dct[ch] = dct[ch] + 1
	else:
		dct[ch] = 1
summ = 0
for k in dct.keys():
	summ += dct[k] // 2
	dct[k] = (dct[k] // 2, summ)
result = 1
for key in dct.keys():
	(k, n) = dct[key]
	result = result * comb(n, k) % int('1' + '0' * 8 + '7')
print(result)


import collections, math, sys
s = sys.stdin.readline().strip()
c = collections.Counter(s)
n = math.factorial(sum((v // 2 for v in c.values())))
for v in c.values():
	if v > 1:
		n //= math.factorial(v // 2)
print(n % 1000000007)


import collections
import math
__author__ = 'max'

def multinomial_coeff(n, r_list):
	result = math.factorial(n)
	for r in r_list:
		result //= math.factorial(r)
	return result

def main():
	string = input()
	letter_counts = collections.Counter(string)
	r_list = (c // 2 for c in letter_counts.values())
	print(multinomial_coeff(len(string) // 2, r_list) % (10 ** 9 + 7))
main()


import math
st = input()
D = {}
for i in st:
	if i in D:
		D[i] += 1
	else:
		D[i] = 1
res = math.factorial(len(st) // 2)
for i in D:
	D[i] //= 2
	res //= math.factorial(D[i])
print(res % (10 ** 9 + 7))


import math
from collections import Counter

def getAnswer(word):
	counter = Counter(word)
	total_palindromes = 1
	total_positions = 0
	for (char, count) in counter.items():
		total_positions += count
		if count % 2 == 1:
			total_positions -= 1
	total_positions //= 2
	for (char, count) in counter.items():
		if count % 2 == 1:
			count -= 1
		count //= 2
		if count == 0:
			continue
		total_palindromes *= math.factorial(total_positions) // (math.factorial(count) * math.factorial(total_positions - count))
		total_palindromes %= 1000000007
		total_positions -= count
	return total_palindromes

def main():
	word = input()
	print(getAnswer(word))
main()


def fact(n):
	res = 1
	for i in range(1, n + 1):
		res *= i
	return res
modulo = 10 ** 9 + 7
s = input().strip()
n = len(s)
count = [0] * 26
ai = ord('a')
for i in range(n):
	count[ord(s[i]) - ai] += 1
for i in range(26):
	count[i] //= 2
n //= 2
res = fact(n)
for i in range(26):
	res //= fact(count[i])
res %= modulo
print(res)


from collections import Counter
from math import factorial as fact
s = input()
(n, freq) = (len(s), Counter(s).values())
if n % 2 != 0:
	n -= 1
	freq = [x if x % 2 == 0 else x - 1 for x in freq]
freq = [i // 2 for i in freq if i > 0]
n //= 2
ans = fact(n)
for i in freq:
	ans //= fact(i)
print(ans % 1000000007)


from math import factorial
NONCE = 10 ** 9 + 7
s = input()
A = [0] * 26
for i in s:
	A[ord(i) - ord('a')] += 1
div = 1
for i in A:
	if i > 1:
		div *= factorial(i // 2)
ans = factorial(len(s) // 2) // div % NONCE
print(int(ans))


import collections, math, sys
s = sys.stdin.readline().strip()
c = collections.Counter(s)
n = math.factorial(sum((v // 2 for v in c.values())))
for v in c.values():
	if v > 1:
		n //= math.factorial(v // 2)
print(n % 1000000007)


from collections import Counter
MOD = 10 ** 9 + 7

def main():
	ltrctr = Counter(input())
	lens = []
	odds = 0
	for count in ltrctr.values():
		odds += count & 1
		lens.append(count // 2)
	if odds > 1:
		print(0)
	num = fact(sum(lens))
	den = 1
	for i in lens:
		den = den * fact(i) % MOD
	print(num * pow(den, MOD - 2, MOD) % MOD)

def fact(n):
	ans = 1
	for i in range(1, n + 1):
		ans = ans * i % MOD
	return ans
main()


from collections import Counter
from math import factorial
candidate = input()
counts = Counter(candidate)
pairs = []
unpaired = 0
for i in counts:
	n = counts[i]
	numPair = n // 2
	if n % 2 == 1:
		unpaired += 1
	if numPair:
		pairs.append(numPair)
denom = 1
for i in pairs:
	denom *= factorial(i)
print(factorial(sum(pairs)) // denom % 1000000007)


import collections, math, sys
s = sys.stdin.readline().strip()
c = collections.Counter(s)
n = math.factorial(sum((v // 2 for v in c.values())))
for v in c.values():
	if v > 1:
		n //= math.factorial(v // 2)
print(n % 1000000007)


import math
mod = 10 ** 9 + 7
chars = list(input())
counts = {}
found_pivot = False
length = len(chars) // 2
total = math.factorial(length)
for c in chars:
	if c in counts:
		counts[c] += 1
	else:
		counts[c] = 1
for key in counts:
	count = counts[key]
	if count % 2 != 0:
		if found_pivot:
			total = 0
			break
		else:
			foud_pivot = True
			count -= 1
	count = count // 2
	total = total // math.factorial(count)
print(total % mod)


import math
anaString = input()
anaList = list(anaString)
uniList = list(set(anaList))
arrayCount = list()
for i in range(len(uniList)):
	tot = 0
	for j in range(len(anaList)):
		if uniList[i] == anaList[j]:
			tot = tot + 1
	arrayCount.append(tot)
halfCount = [x // 2 for x in arrayCount]
mod = math.pow(10, 9) + 7
mod = int(mod)
ans = 1
num = math.factorial(sum(arrayCount) // 2)
den = 1
for i in range(len(halfCount)):
	den = den * math.factorial(halfCount[i])
num = int(num)
den = int(den)
ans = num // den
ans = ans % mod
print(ans)


from collections import Counter
from math import factorial

def nCr(n, r):
	return factorial(n) // (factorial(r) * factorial(n - r))
mod = 10 ** 9 + 7
letterCounts = Counter(input())
halfNums = []
numPalindromes = 1
for letter in letterCounts:
	halfNums.append(letterCounts[letter] // 2)
total = sum(halfNums)
for num in halfNums:
	numPalindromes = numPalindromes * nCr(total, num) % mod
	total -= num
print(numPalindromes)


import collections
import math
MOD = 10 ** 9 + 7
S = input().rstrip()
dic = collections.defaultdict(int)
for x in S:
	dic[x] += 1
num = [x // 2 for x in dic.values()]
total = sum(num)
res = math.factorial(total)
for x in num:
	res = res // math.factorial(x)
print(res % MOD)


from collections import defaultdict
mod = 10 ** 9 + 7

def choose(n, k):
	if n < len(ccache):
		return ccache[n][k]
	else:
		p = 1
		for i in range(k):
			p = p * (n - i) // (i + 1)
		return p % mod
s = input().strip()
cs = defaultdict(lambda : 0)
for c in s:
	cs[c] += 1
hl = len(s) // 2
ccache = [[1]]
for i in range(min(hl, 2000)):
	ccache.append([1] + [(ccache[-1][j] + ccache[-1][j + 1]) % mod for j in range(i)] + [1])
c = 1
for n in cs.values():
	k = n // 2
	c = c * choose(hl, k) % mod
	hl -= k
print(c)


import collections, math, sys
s = sys.stdin.readline().strip()
c = collections.Counter(s)
n = math.factorial(sum((v // 2 for v in c.values())))
for v in c.values():
	if v > 1:
		n //= math.factorial(v // 2)
print(n % 1000000007)


import collections, math, sys
s = sys.stdin.readline().strip()
c = collections.Counter(s)
n = math.factorial(sum((v // 2 for v in c.values())))
for v in c.values():
	if v > 1:
		n //= math.factorial(v // 2)
print(n % 1000000007)


from math import factorial

def getAnswer(word):
	counts = [0 for i in range(26)]
	for c in word:
		counts[ord(c) - 97] += 1
	perms = [x // 2 for x in counts]
	div = 1
	for x in perms:
		div *= factorial(x)
	return factorial(sum(perms)) // div % (10 ** 9 + 7)

def main():
	word = input()
	print(getAnswer(word))
main()


import collections, math, sys
s = sys.stdin.readline().strip()
c = collections.Counter(s)
n = math.factorial(sum((v // 2 for v in c.values())))
for v in c.values():
	if v > 1:
		n //= math.factorial(v // 2)
print(n % 1000000007)


import collections, math, sys
s = sys.stdin.readline().strip()
c = collections.Counter(s)
n = math.factorial(sum((v // 2 for v in c.values())))
for v in c.values():
	if v > 1:
		n //= math.factorial(v // 2)
print(n % 1000000007)


import collections, math, sys
s = sys.stdin.readline().strip()
c = collections.Counter(s)
n = math.factorial(sum((v // 2 for v in c.values())))
for v in c.values():
	if v > 1:
		n //= math.factorial(v // 2)
print(n % 1000000007)


def fact_mod_p_brute(n, p):
	if n == 0:
		return 1
	res = 1
	for i in range(1, n + 1):
		res *= i
		res = res % p
	return res
s2 = [0 for i in range(270)]
s = str(input())
for l in s:
	s2[ord(l)] += 1
c = 0
sum = 0
for i in range(270):
	if s2[i] % 2 == 1:
		c += 1
	s2[i] //= 2
	sum += s2[i]
pp = 1000000007
if c > 1:
	print('0')
else:
	licz = fact_mod_p_brute(sum, pp)
	mian = 1
	for i in range(270):
		mian *= fact_mod_p_brute(s2[i], pp)
		mian = mian % pp
	print(licz * pow(mian, pp - 2, pp) % pp)


from collections import Counter
from math import factorial as f
teststr = input()
tot = f(len(teststr) // 2)
for (y, x) in Counter(teststr).items():
	tot //= f(x // 2)
print(tot % (10 ** 9 + 7))


s = str(input())
mod = 10 ** 9 + 7
cnt = {}
for x in s:
	if x in cnt:
		cnt[x] += 1
	else:
		cnt[x] = 1
odd_cnt = 0
nums = []
for x in cnt.keys():
	if cnt[x] % 2 == 1:
		odd_cnt += 1
	nums.append(cnt[x] // 2)
if odd_cnt > 1:
	print(0)
else:
	sums = sum(nums)
	fact = [1] * (sums + 1)
	for i in range(1, sums + 1):
		fact[i] = fact[i - 1] * i % mod
	ans = fact[sums]
	for x in nums:
		if x == 0:
			continue
		ans *= pow(fact[x], mod - 2, mod)
		ans %= mod
	print(ans)


from string import ascii_lowercase
from functools import reduce
p = 1000000007
max_n = 50001
factorial = [1] * max_n
inv_factorial = [1] * max_n

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	(g, y, x) = egcd(b % a, a)
	return (g, x - b // a * y, y)

def mod_inv(a, m):
	(gcd, x, y) = egcd(a, m)
	if gcd != 1:
		return None
	return x % m

def mul_m(a, b):
	return a * b % p
for i in range(1, max_n):
	factorial[i] = i * factorial[i - 1] % p
	inv_factorial[i] = mod_inv(i, p) * inv_factorial[i - 1] % p
string = input()
counts = {}
for ch in ascii_lowercase:
	counts[ch] = 0
for ch in string:
	counts[ch] += 1
print(reduce(mul_m, [inv_factorial[count // 2] for count in counts.values()], factorial[len(string) // 2]))


MOD = 1000000007
from collections import Counter
from math import factorial
C = Counter(input())
a = 0
b = 1
for k in C:
	c = C[k]
	a += c >> 1
	b *= factorial(c >> 1)
print(factorial(a) // b % MOD)


n = input().strip()
razlicni = []
koliko = []
for x in n:
	if x not in razlicni:
		razlicni += [x]
odgovor = 0
lihih = 0
for x in razlicni:
	r = 0
	for g in n:
		if g == x:
			r += 1
	koliko += [r]
	if r % 2 == 1:
		lihih += 1

def fak(n):
	if n < 2:
		return 1
	else:
		a = 1
		b = 1
		while a <= n:
			b *= a
			a += 1
		return b

def resitev(e):
	r = 0
	rr = 1
	for x in e:
		r += x // 2
		rr *= fak(x // 2)
	m = fak(r) // rr
	return m % 1000000007
odgovor = resitev(koliko)
print(odgovor)


import string

def add_to_arr(arr, k, plus=1):
	i = 2
	while i * i <= k:
		while k % i == 0:
			arr[i] += plus
			k //= i
		i += 1
	if k > 1:
		arr[k] += plus

def add_all(arr, n, plus=1):
	for i in range(n + 1):
		add_to_arr(arr, i, plus)
res = [0] * 10 ** 5
word = input()
odd = 0
add_all(res, len(word) // 2)
for c in string.ascii_lowercase:
	num = word.count(c)
	odd += num % 2
	add_all(res, num // 2, -1)
if odd > 1:
	print(0)
else:
	res2 = 1
	for (a, b) in enumerate(res):
		if a < 2:
			continue
		res2 *= a ** b
		res2 %= 10 ** 9 + 7
	print(res2)


from collections import Counter
from functools import reduce
from operator import floordiv
from math import factorial
c = [x // 2 for x in Counter(input()).values()]
print(reduce(floordiv, (factorial(x) for x in c), factorial(sum(c))) % int(1000000000.0 + 7))


from math import factorial, log

def factorial_large(x, mod):
	total = 1
	while x > 0:
		total = total * x % mod
		x -= 1
	return total

def exponentiation_large(x, n, mod):
	if n == 0:
		return 1
	elif n == 1:
		return x % mod
	if n % 2 == 0:
		total = exponentiation_large(x, n // 2, mod) ** 2
	else:
		total = exponentiation_large(x, n - 1, mod) * x
	return total % mod

def main():
	letters = input()
	mod = 10 ** 9 + 7
	answer = 51681694264200 % mod
	counts = {}
	for letter in letters:
		if letter not in counts:
			counts[letter] = 1
		else:
			counts[letter] += 1
	psl = 0
	for (letter, count) in counts.items():
		psl += count // 2
	output = factorial_large(psl, mod)
	for (letter, count) in counts.items():
		for i in range(1, count // 2 + 1):
			exp = exponentiation_large(i, mod - 2, mod)
			output = output * exp % mod
	print(output)
main()


from sys import stdin
from itertools import accumulate as acc, count, combinations_with_replacement as cmbrep, takewhile as tkw, repeat as rp, dropwhile as dpw, combinations as comb
from functools import reduce
from random import randint
from collections import Counter
from math import sqrt, log, factorial
modo = 10 ** 9 + 7

def inv(N):
	return pow(N, modo - 2, modo)

def factMod(N):
	return reduce(lambda x, y: x * y % modo, range(2, N + 1), 1)

def faire(ch):
	cnt = Counter(ch)
	cm = factMod(sum(cnt.values()) // 2)
	return reduce(lambda x, y: x * inv(factMod(y // 2)) % modo, cnt.values(), cm)
rd = stdin
print(faire(rd.readline().strip()))


def fact(n):
	m = 1
	for i in range(1, n + 1):
		m *= i
	return m
str = input()
alp = []
for i in range(0, 26):
	alp.insert(i, 0)
for letter in str:
	n = ord(letter) - 97
	x = alp[n] + 1
	del alp[n]
	alp.insert(n, x)
count = 0
div = []
j = 0
for i in alp:
	if i % 2 != 0 and i > 1:
		count += (i - 1) / 2
		div.insert(j, (i - 1) // 2)
	if i % 2 == 0 and i > 0:
		count += i / 2
		div.insert(j, i // 2)
	j += 1
x = 1
for i in div:
	x *= fact(i)
print(fact(int(count)) // x % 1000000007)


import string
import math
from collections import Counter
P = 10 ** 9 + 7

def cnr(n, r):
	x = 1
	if r == n:
		return 1
	for k in range(n - r + 1, n + 1):
		x = x * k
	return x // math.factorial(r)

def solve(s):
	f = Counter(s)
	has_odd = len([k for (k, v) in f.items() if v % 2 == 1]) == 1
	n = len(s) // 2
	total = 1
	for c in string.ascii_lowercase:
		r = f[c] // 2
		total = total * cnr(n, r) % P
		n -= r
	return int(total)
s = input()
print(solve(s))


from collections import Counter
import math
s = input()
c = Counter(s)
l = len(s) // 2
count = math.factorial(l)
for v in c.values():
	count //= math.factorial(v // 2)
print(count % (10 ** 9 + 7))


import math
fact = math.factorial
w = input()
sc = [w.count(chr(l)) for l in range(int(ord('a')), int(ord('z') + 1))]
odd = []
i = 0
for c in sc:
	if c % 2 == 1:
		odd.append(i)
	i += 1
for i in range(0, len(sc)):
	sc[i] = math.floor(sc[i] / 2)
sz = math.floor(len(w) / 2)
combos = 1

def C(a, b):
	return int(fact(a) // (fact(b) * fact(a - b)))

def P(a, b):
	return int(fact(a) // fact(a - b))
for c in sc:
	combos = combos * C(sz, c) % 1000000007
	sz -= c
print(combos)


import math
fact = [1]
m = 10 ** 9 + 7
for i in range(100000):
	fact.append(fact[i] * (i + 1) % m)
L = list(input())
F = [0] * 27
for i in range(len(L)):
	F[ord(L[i]) - 97] += 1
s = 1
n = 0
y = 0
for i in range(26):
	y += F[i] % 2
	if y > 1:
		print(0)
		exit()
for i in range(26):
	if F[i] == 0:
		continue
	s = s * fact[int(F[i] // 2)] % m
	n += int(F[i] // 2)
print(fact[n] * pow(s, m - 2, m) % m)


import math
a = input()
b = [0] * 26
for i in a:
	b[ord(i) - ord('a')] = b[ord(i) - ord('a')] + 1
dist = 0
for j in range(len(b)):
	if b[j] % 2 == 0:
		dist = dist + b[j] // 2
	else:
		b[j] = b[j] - 1
		dist = dist + b[j] // 2
ans = math.factorial(dist)
for u in b:
	if u % 2 == 0:
		ans = ans // math.factorial(u // 2)
print(ans % 1000000007)


import math
s = input().strip()
d = dict()
for char in s:
	if d.get(char, None) is None:
		d[char] = 1
	else:
		d[char] += 1
result = math.factorial(len(s) // 2)
for key in d.keys():
	result //= math.factorial(d[key] // 2)
print(int(result) % (10 ** 9 + 7))


from collections import defaultdict
from math import factorial

def checkPalin(s):
	setS = list(set(s))
	count = 0
	for i in setS:
		if s.count(i) % 2 == 1:
			count += 1
		if count > 1:
			return False
	return True

def countPalin(s):
	counter = defaultdict(int)
	for item in s:
		counter[item] += 1
	n = len(s) // 2
	ans = factorial(n)
	for val in counter.values():
		ans = ans // factorial(val // 2)
	return int(ans % MOD)
MOD = 10 ** 9 + 7
s = input().strip()
if checkPalin(s):
	print(countPalin(s))
else:
	print(0)


import collections, math, sys
s = sys.stdin.readline().strip()
c = collections.Counter(s)
n = math.factorial(sum((v // 2 for v in c.values())))
for v in c.values():
	if v > 1:
		n //= math.factorial(v // 2)
print(n % 1000000007)


def C(n, k):
	res = 1
	div = 1
	for i in range(k):
		res *= n - i
		div *= k - i
	return res // div
l = input()
count = [0] * 26
for i in l:
	count[ord(i) - ord('a')] += 1
count = list(map(lambda x: x // 2, count))
length = len(l) // 2
res = 1
mod = 10 ** 9 + 7
for i in count:
	if i != 0:
		res = res * C(length, i) % mod
		length -= i
print(res)


MOD = 10 ** 9 + 7

def inv(x):
	(a, ap, r, rp) = (1, 0, x, MOD)
	while r > 1:
		(a, ap, r, rp) = (ap - rp // r * a, a, rp % r, r)
	return a
s = input()
count = [0] * 26
for i in s:
	count[ord(i) - ord('a')] += 1
for i in range(26):
	count[i] //= 2
n = sum(count)
fact = [1] * (n + 1)
finv = [1] * (n + 1)
for i in range(2, n + 1):
	fact[i] = i * fact[i - 1] % MOD
	finv[i] = inv(i) * finv[i - 1] % MOD
p = fact[n]
for i in count:
	p = p * finv[i] % MOD
print(p)


s = input().strip()
n = len(s)
D = dict()
p = 10 ** 9 + 7
F = [1]
for i in range(1, 10 ** 5 + 1):
	F.append(F[i - 1] * i % p)
for i in range(n):
	D[s[i]] = D.get(s[i], 0) + 1
bad = 0
A = []
for x in D:
	if D[x] % 2 == 1:
		bad += 1
		if D[x] != 1:
			A.append(D[x] // 2)
	else:
		A.append(D[x] // 2)
if bad > 1:
	print(0)
else:
	ans = F[sum(A)]
	for i in range(len(A)):
		ans *= pow(F[A[i]], p - 2, p)
		ans %= p
	print(ans)


def bitize(x):
	L = []
	while x > 0:
		L.append(x % 2)
		x //= 2
	if L == 0:
		L.append(0)
	return L

def pow_mod(a, b, m):
	b_bits = bitize(b)
	a_powers = [0 for x in b_bits]
	a_powers[0] = a % m
	if b_bits[0]:
		total = a % m
	else:
		total = 1
	for i in range(1, len(b_bits)):
		a_powers[i] = a_powers[i - 1] * a_powers[i - 1] % m
		if b_bits[i]:
			total *= a_powers[i]
			total %= m
	return total % m

def is_prime(x, L=[]):
	sqrt = int(pow(x, 0.5)) + 1
	PL = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 16, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199]
	if not L:
		if x < 210:
			if x in PL:
				return True
			else:
				return False
		else:
			for p in PL:
				if x % p == 0:
					return False
			for i in range(1, sqrt // 210 + 1):
				for j in [1, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 121, 127, 131, 137, 139, 143, 149, 151, 157, 163, 167, 169, 173, 179, 181, 187, 191, 193, 197, 199, 209]:
					if x % (210 * i + j) == 0:
						return False
		return True
	elif x != 0 and x != 1:
		j = 0
		while j < len(L) and L[j] <= sqrt:
			if x % L[j] == 0:
				return False
			j += 1
	else:
		return False
	return True

def prime_list(n):
	L = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199]
	for k in range(1, n // 210):
		for j in [1, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 121, 127, 131, 137, 139, 143, 149, 151, 157, 163, 167, 169, 173, 179, 181, 187, 191, 193, 197, 199, 209]:
			if is_prime(210 * k + j, L):
				L.append(210 * k + j)
	k = n // 210
	for j in [1, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 121, 127, 131, 137, 139, 143, 149, 151, 157, 163, 167, 169, 173, 179, 181, 187, 191, 193, 197, 199, 209]:
		if is_prime(210 * k + j, L) and 210 * k + j <= n:
			L.append(210 * k + j)
	return L

def bucketify(s):
	B = [0 for x in range(0, 26)]
	for i in range(0, len(s)):
		B[ord(s[i]) - ord('a')] += 1
	odd_one = -1
	for j in range(0, 26):
		if B[j] % 2:
			odd_one = j
		B[j] //= 2
	return (B, odd_one)

def compute_factorial_mod(n, modulus, PL):
	fact = 1
	for p in PL:
		m = n
		total_power = 0
		while m > 0:
			m //= p
			total_power += m
		if total_power == 0:
			return fact
		else:
			fact *= pow_mod(p, total_power, modulus)
	return fact

def compute_multi_permutations(buckets, modulus):
	PL = prime_list(100000)
	n_fact = compute_factorial_mod(sum(buckets), modulus, PL)
	buckets_fact = [compute_factorial_mod(b, modulus, PL) for b in buckets]
	inverses_fact = [pow_mod(b, modulus - 2, modulus) for b in buckets_fact]
	result = n_fact
	for i in inverses_fact:
		result *= i
		result %= modulus
	return result
modulus = pow(10, 9) + 7
s = input()
(buckets, odd_one) = bucketify(s)
print(compute_multi_permutations(buckets, modulus))


m = [0 for i in range(26)]
s = input()
for i in s:
	m[ord(i) - ord('a')] += 1
res = 1
n = len(s) // 2
z = [i // 2 for i in m if i > 1]
ch = zn = 1
mod = 10 ** 9 + 7
for i in z:
	for j in range(i):
		ch *= n - j
		ch %= mod
		zn *= j + 1
		zn %= mod
	n -= i
print(ch * pow(zn, mod - 2, mod) % mod)


from math import factorial, log

def fact_large(x, mod):
	total = 1
	while x > 0:
		total = total * x % mod
		x -= 1
	return total

def exp_large(x, n, mod):
	if n == 0:
		return 1
	elif n == 1:
		return x % mod
	if n % 2 == 0:
		total = exp_large(x, n // 2, mod) ** 2
	else:
		total = exp_large(x, n - 1, mod) * x
	return total % mod

def main():
	letters = input()
	mod = 10 ** 9 + 7
	answer = 51681694264200 % mod
	counts = {}
	for letter in letters:
		if letter not in counts:
			counts[letter] = 1
		else:
			counts[letter] += 1
	psl = 0
	for (letter, count) in counts.items():
		psl += count // 2
	output = fact_large(psl, mod)
	for (letter, count) in counts.items():
		for i in range(1, count // 2 + 1):
			exp = exp_large(i, mod - 2, mod)
			output = output * exp % mod
	print(output)
main()


import math
import sys
s = input().strip()
l = []
s = list(s)
for i in range(26):
	l.append(0)
for i in range(len(s)):
	l[ord(s[i]) - 97] += 1
sums = 0
for i in range(26):
	if l[i] != 0 and l[i] % 2 != 0:
		l[i] -= 1
	if l[i] != 0:
		l[i] /= 2
sums = sum(l)
numr = math.factorial(sums)
for i in range(26):
	if l[i] == 0:
		continue
	val = math.factorial(l[i])
	numr = int(numr // val)
print(int(numr % (10 ** 9 + 7)))


from collections import Counter
P = 10 ** 9 + 7
N = 10 ** 5 + 1
F = [1] * N
for n in range(2, N):
	F[n] = n * F[n - 1] % P

def inv(n):
	return pow(n, P - 2, P)

def anacount(S):
	C = Counter(S)
	if sum((C[c] % 2 for c in C)) > 1:
		return 0
	res = F[len(S) // 2]
	for c in C:
		res = res * inv(F[C[c] // 2]) % P
	return res
S = input().strip()
print(anacount(S))