def nArModp(n,r,p):
    res = 1
    for i in range(r+1,n+1):
        res= (res*i)%p
    return res

def nTorModp(n,r,p):
    if (n>p) or (r> p-1):
        return nTorModp(n%p,r%(p-1),p)
    if r==0:
        return 1
    if r%2:
        return (n*nTorModp(n,r-1,p))%p
    else:
        return (nTorModp(n,r//2,p)**2)%p
    
    
def nCmultrModp(arr,p):
    N=sum(arr)
    arr=sorted(arr)
    res =1
    rold=0
    lr = len(arr)
    #denominator
    for i,r in enumerate(arr[:lr-1]):
        res = res * (nTorModp(nArModp(r,rold,p),lr-1-i,p)) % p
        rold=r
    #numerator
    rNum = nArModp(N,arr[lr-1],p)
    return (nTorModp(res,p-2,p)*rNum)%p
    


def solve(s):
    counts = list(Counter(s).values())
    counts = [c//2 for c in counts if c > 1]
    return nCmultrModp(counts,10**9+7)

def solve(s):
    # Write your code here
    num=int(len(s)/2)

    ca=math.factorial(num)

    cou=Counter(s)

    for i in cou:
        ca=ca//math.factorial(int(cou[i]/2))

    return (ca%((10**9)+7))

def solve(s)
    counts = s.split('').group_by{|x|x}.values.map{|v| v.size/2}
    (1..counts.sum).reduce(:*)/(counts.map{|c| (1..c).reduce(:*) || 1}.reduce(:*))%(10**9+7)
end

# Pythonic Way
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 //= factorial(val//2)        
    return (ans % MOD)