from collections import Counter
from math import factorial

total = 0

class Solution(object):
    def numTilePossibilities(self, tiles):
        """
        :type tiles: str
        :rtype: int
        """
        
        
        dict = Counter(tiles)

        input = [x for x in dict.keys()]
        count = [x for x in dict.values()]
        
        def comb(output, pos, input, count):
            global total
            for i in range(pos, len(input)):
                if count[i] == 0:
                    continue

                output.append(input[i])
                d = Counter(output)

                perm = factorial(len(output))
                for x in d.values():
                    perm = perm/factorial(x)
                total += perm
                count[i] -= 1
                comb(output, i, input, count)
                count[i] += 1
                output.pop()
                
        comb([], 0, input, count)

    return total