This night wasn't easy on Vasya. His favorite team lost, and he didn't find himself victorious either — although he played perfectly, his teammates let him down every time. He had to win at least one more time, but the losestreak only grew longer and longer... It's no wonder he didn't get any sleep this night at all.

In the morning, Vasya was waiting the bus to the university on the bus stop. Vasya's thoughts were hazy and so he couldn't remember the right bus' number quite right and got onto the bus with the number $n$.

In the bus, Vasya thought that he could get the order of the digits in the number of the bus wrong. Futhermore, he could "see" some digits several times, but the digits he saw were definitely in the real number of the bus. For example, if Vasya saw the number 2028, it could mean that the real bus number could be 2028, 8022, 2820 or just 820. However, numbers 80, 22208, 52 definitely couldn't be the number of the bus. Also, real bus number couldn't start with the digit 0, this meaning that, for example, number 082 couldn't be the real bus number too.

Given $n$, determine the total number of possible bus number variants.


-----Input-----

The first line contains one integer $n$ ($1 \leq n \leq 10^{18}$) — the number of the bus that was seen by Vasya. It is guaranteed that this number does not start with $0$.


-----Output-----

Output a single integer — the amount of possible variants of the real bus number.


-----Examples-----
Input
97

Output
2

Input
2028

Output
13



-----Note-----

In the first sample, only variants $97$ and $79$ are possible.

In the second sample, the variants (in the increasing order) are the following: $208$, $280$, $802$, $820$, $2028$, $2082$, $2208$, $2280$, $2802$, $2820$, $8022$, $8202$, $8220$.

Difficulty: MEDIUM_HARD
Tags: Combinatorics

Mathematics

Complete search
Skill types: Complete search

Starter code:

Solutions:
from collections import Counter
from itertools import product
s = input()
ds = Counter(s)
fac = [1 for i in range(100)]
for i in range(1, 100):
	fac[i] = fac[i - 1] * i
res = 0
for possib in product(*[zip([k] * n, range(1, n + 1)) for (k, n) in ds.items()]):
	possib = list(possib)
	non_zero_sum = sum((v for (k, v) in possib if k != '0'))
	total = sum((v for (_, v) in possib))
	value = non_zero_sum * fac[total - 1]
	for (_, v) in possib:
		value //= fac[v]
	res += value
print(res)


import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
import collections
from itertools import permutations
from collections import defaultdict
from collections import deque
import threading
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class SegmentTree:

	def __init__(self, data, default=-10 ** 6, func=lambda a, b: max(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree1:

	def __init__(self, data, default=10 ** 6, func=lambda a, b: min(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)
MOD = 10 ** 9 + 7

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD
mod = 10 ** 9 + 7
omod = 998244353
prime = [True for i in range(200001)]
pp = [0] * 200001

def SieveOfEratosthenes(n=200000):
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
N = input()
C = [0] * 10
for n in N:
	C[int(n)] += 1
memo = {}

def dfs(i, state):
	key = tuple(state)
	if key in memo:
		return memo[key]
	r = 0
	if all((s == 0 or 1 <= t for (s, t) in zip(C, state))):
		r += 1
	for j in range(10):
		if C[j] - state[j] > 0:
			state[j] += 1
			r += dfs(i + 1, state)
			state[j] -= 1
	memo[key] = r
	return r
state = [0] * 10
ans = 0
for i in range(1, 10):
	if C[i] > 0:
		state[i] += 1
		ans += dfs(1, state)
		state[i] -= 1
print(ans)


s = input()
occ = [0] * 10
for c in s:
	occ[int(c)] += 1
from math import factorial as fact
from itertools import combinations
from collections import Counter

def multinomial(L):
	res = fact(sum(L))
	for x in L:
		res //= fact(x)
	if L[0] == 0:
		return res
	L[0] -= 1
	lead0 = fact(sum(L))
	for x in L:
		lead0 //= fact(x)
	L[0] += 1
	return res - lead0

def dfs(i):
	if i == 10:
		return multinomial(rocc)
	ans = 0
	for j in range(rocc_ini[i], occ[i] + 1):
		rocc[i] = j
		ans += dfs(i + 1)
	return ans
rocc = [0] * 10
for i in range(10):
	if occ[i]:
		rocc[i] += 1
rocc_ini = rocc[:]
print(dfs(0))


import math
fact = [math.factorial(x) for x in range(20)]

def product(L):
	ans = 1
	for i in L:
		ans *= i
	return ans

def count(digits):
	s = sum(digits)
	return fact[s] // product([fact[i] for i in digits])
n = input()
strn = str(n)
digs = [0 for i in range(10)]
for let in strn:
	dig = int(let)
	digs[dig] += 1
zeroes = digs[0]
others = digs[1:]
while 0 in others:
	others.remove(0)
digs = [zeroes] + others

def answer(digits, chosen=[]):
	ans = 0
	if digits == []:
		return helper(chosen)
	if digits[0] == 0:
		return answer(digits[1:], chosen + [0])
	for i in range(1, digits[0] + 1):
		ans += answer(digits[1:], chosen + [i])
	return ans

def helper(chosen):
	if chosen[0] == 0:
		return count(chosen)
	alt = chosen.copy()
	alt[0] -= 1
	return count(chosen) - count(alt)
print(answer(digs))


from collections import defaultdict
n = [int(i) for i in input()]
st = frozenset(n)
ini = [n.count(i) for i in range(10)]
dp = defaultdict(int)

def dfs(state):
	key = tuple(state)
	if key in dp:
		return dp[key]
	if all((state[i] > 0 for i in st)):
		dp[key] += 1
	for i in range(10):
		if state[i] < ini[i]:
			state[i] += 1
			dp[key] += dfs(state)
			state[i] -= 1
	return dp[key]
ans = 0
s = [0] * 10
for i in range(1, 10):
	if ini[i]:
		s[i] = 1
		ans += dfs(s)
		s[i] = 0
print(ans)


def fact(x):
	i = 2
	res = 1
	while i <= x:
		res = res * i
		i = i + 1
	return res
inp = input()
arr = []
for i in range(len(inp)):
	arr.append(int(inp[i]))
have = [0] * 10
for i in range(len(arr)):
	have[arr[i]] = have[arr[i]] + 1
cur = [0] * 10

def add(n):
	res = 0
	for i in range(1, 10):
		if cur[i] > 0:
			cur[i] = cur[i] - 1
			now = fact(n - 1)
			for j in range(10):
				now = now // fact(cur[j])
			res = res + now
			cur[i] = cur[i] + 1
	return res

def rec(i, n):
	if i == 10:
		return add(n)
	else:
		if have[i] == 0:
			return rec(i + 1, n)
		else:
			res = 0
			for t in range(1, have[i] + 1):
				cur[i] = t
				res = res + rec(i + 1, n + t)
		return res
print(rec(0, 0))


n = input()
fact = [1]
for i in range(len(n)):
	fact.append((i + 1) * fact[-1])
times = [0 for i in range(10)]
for val in n:
	times[int(val)] += 1

def yoyo(vect):
	l = sum(vect)
	temp = fact[l - 1] * (l - vect[0])
	for j in range(10):
		temp /= fact[vect[j]]
	return temp

def recursive(a, pos):
	if pos == 10:
		return yoyo(a)
	temp_ans = 0
	if times[pos] == 0:
		temp_ans += recursive(a, pos + 1)
	for i in range(times[pos]):
		a[pos] += 1
		temp_ans += recursive(a, pos + 1)
	a[pos] = 0
	return temp_ans
ans = 0
print(int(recursive([0 for i in range(10)], 0)))


a = []
fact = []

def find(num, val, cnt):
	global ans
	if num == 10:
		ans += val * fact[cnt]
		return
	if a[num] >= 1:
		i = 1
		while i <= a[num]:
			num += 1
			val = val / fact[i]
			cnt += i
			find(num, val, cnt)
			num -= 1
			val = val * fact[i]
			cnt -= i
			i += 1
	else:
		num += 1
		find(num, val, cnt)
		num -= 1

def find1(num, val, cnt):
	global ans
	if num == 10:
		ans -= val * fact[cnt]
		return
	if a[num] >= 1:
		i = 1
		if num == 0:
			i = 0
		while i <= a[num]:
			num += 1
			val = val / fact[i]
			cnt += i
			find1(num, val, cnt)
			num -= 1
			val = val * fact[i]
			cnt -= i
			i += 1
	else:
		num += 1
		find1(num, val, cnt)
		num -= 1
n = int(input())
for i in range(10):
	a.append(0)
fact.append(1)
for i in range(1, 20):
	fact.append(fact[i - 1] * i)
m = n
while m > 0:
	a[m % 10] += 1
	m = m // 10
ans = 0
find(0, 1, 0)
if a[0] != 0:
	a[0] -= 1
	find1(0, 1, 0)
print(int(ans))


P = 23

def f(a):
	bomb = 0
	for i in range(0, 10):
		bomb += P ** i * (a[i] + 1)
	return bomb

def rec(n, a):
	d[f(a)] = True
	ans = fact[n]
	if a[0] != 0:
		ans -= a[0] * fact[n - 1]
	temp = 0
	for i in range(0, 10):
		if a[i] > 1:
			ans //= fact[a[i]]
			a[i] -= 1
			if d.get(f(a)) == None:
				temp += rec(n - 1, a)
			a[i] += 1
	return ans + temp
s = str(input())
n = len(s)
fact = []
fact.append(1)
for i in range(1, 30):
	fact.append(fact[i - 1] * i)
d = {}
a = []
for i in range(10):
	a.append(0)
for i in range(n):
	a[ord(s[i]) - ord('0')] += 1
print(int(rec(n, a)))


a = int(input())
b = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
while a != 0:
	b[a % 10] += 1
	a //= 10
ans = 0

def gao(n):
	f = 1
	for i in range(1, n + 1):
		f *= i
	return f

def shit(n, arr):
	global ans
	if n == 10:
		sum = 0
		for i in range(10):
			sum += arr[i]
		gg = sum - arr[0]
		gg *= gao(sum - 1)
		for i in range(10):
			if arr[i] > 1:
				gg //= gao(arr[i])
		ans += gg
	elif b[n] > 0:
		for i in range(1, b[n] + 1):
			gg = arr.copy()
			gg.append(i)
			shit(n + 1, gg)
	else:
		arr.append(0)
		shit(n + 1, arr)
shit(0, [])
print(int(ans))


from collections import defaultdict
import math

def com(N, R):
	if not N >= R >= 0:
		return 0
	return math.factorial(N) // (math.factorial(R) * math.factorial(N - R))

def solve():
	a = list(map(int, list(input())))
	L = len(a)
	d = defaultdict(int)
	for v in a:
		d[v] += 1
	que = [(key, value) for (key, value) in d.items()]
	que.sort()

	def recursion(index):
		if index == len(que) - 1:
			(num, numcnt) = que[index]
			return [[(num, i)] for i in range(1, numcnt + 1)]
		else:
			res = []
			(num, numcnt) = que[index]
			for i in range(1, numcnt + 1):
				for v in recursion(index + 1):
					add = v.copy()
					add.append((num, i))
					res.append(add)
			return res
	res = recursion(0)
	ans = 0
	for v in res:
		v.reverse()
		vsum = sum((x[1] for x in v))
		S = math.factorial(sum((x[1] for x in v)))
		for x in v:
			S //= math.factorial(x[1])
		if v[0][0] == 0:
			S *= vsum - v[0][1]
			S //= vsum
		ans += S
	print(ans)
	return
solve()


import collections
import itertools
n = input()
fibo = [1]
while len(fibo) <= len(n):
	fibo.append(fibo[-1] * len(fibo))
cnts = collections.defaultdict(int)
for x in n:
	cnts[int(x)] += 1

def get_ans(choices):
	ret = 0
	for choice in choices:
		(a, b) = (0, 1)
		for x in choice:
			a += x
			b *= fibo[x]
		a = fibo[a]
		ret += a // b
	return ret
ans = 0
for i in range(1, 10):
	if cnts[i] == 0:
		del cnts[i]
		continue
	cnts[i] -= 1
	if cnts[i] == 0:
		del cnts[i]
	choices = itertools.product(*(range(key != i, value + 1) for (key, value) in cnts.items()))
	ans += get_ans(choices)
	cnts[i] += 1
print(ans)


def main():
	ast = []

	def fact(x):
		if x == 0:
			return 1
		return x * fact(x - 1)
	n = input()

	def helper(dc):
		a = 0
		temp = [dc[j] for j in dc if j != '0']
		s = sum(temp)
		try:
			ret = fact(s) * fact(s + dc['0'] - 1) // (fact(s - 1) * fact(dc['0']))
		except:
			ret = fact(s)
		for i in temp:
			ret = ret // fact(i)
		for i in dc:
			if dc[i] != 1:
				d = {}
				for j in dc:
					d[j] = dc[j]
				d[i] -= 1
				if str(d) not in ast:
					ast.append(str(d))
					a += helper(d)
		return ret + a
	dct = {}
	for i in set(n):
		dct[i] = n.count(i)
	print(helper(dct))
	return 0
main()


import sys
import math
import collections
from pprint import pprint as pp
mod = 1000000007
MAX = 10 ** 18

def inp():
	return map(int, input().split())

def array():
	return list(map(int, input().split()))

def vector(size, val=0):
	vec = [val for i in range(size)]
	return vec

def matrix(rowNum, colNum, val=0):
	mat = []
	for i in range(rowNum):
		collumn = [val for j in range(colNum)]
		mat.append(collumn)
	return mat

def fact(lim):
	ary = vector(lim + 1, 1)
	for i in range(2, lim + 1):
		ary[i] = ary[i - 1] * i
	return ary

def pascle(lim):
	p = matrix(lim, lim)
	for i in range(lim):
		p[i][i] = p[i][0] = 1
	for i in range(1, lim):
		for j in range(1, lim):
			p[i][j] = p[i - 1][j - 1] + p[i - 1][j]
	return p
n = input()
d = {}
f = fact(25)
p = pascle(25)
for i in range(10):
	d[i] = 0
for i in range(len(n)):
	d[ord(n[i]) - ord('0')] += 1
now = vector(10)
ans = 0

def fun(x):
	global ans
	if x == 10:
		cnt = 0
		for i in range(1, 10):
			cnt += now[i]
		temp = f[cnt]
		for i in range(1, 10):
			temp //= f[now[i]]
		if now[0] > 0 and cnt >= 1:
			temp *= p[now[0] + cnt - 1][cnt - 1]
		ans += temp
	elif d[x] == 0:
		now[x] = 0
		fun(x + 1)
	else:
		for i in range(1, d[x] + 1):
			now[x] = i
			fun(x + 1)
fun(0)
print(ans)


def solve(index, taken, invalids, zeros):
	if index >= 10:
		global sol
		sol += fact[taken] // invalids
		if zeros > 0:
			invalids = invalids // fact[zeros]
			invalids = invalids * fact[zeros - 1]
			sol = sol - fact[taken - 1] // invalids
		return
	if rep[index] == 0:
		solve(index + 1, taken, invalids, zeros)
	for x in range(1, rep[index] + 1):
		if index != 0:
			solve(index + 1, taken + x, invalids * fact[x], zeros)
		else:
			solve(index + 1, taken + x, invalids * fact[x], x)
sol = 0
fact = [1]
for i in range(1, 20):
	fact.append(fact[i - 1] * i)
n = str(input())
rep = [0 for i in range(10)]
for c in n:
	rep[int(c)] += 1
solve(0, 0, 1, 0)
print(sol)


import math
import sys

def newt(n, k):
	return math.factorial(n) // math.factorial(k) // math.factorial(n - k)

def go(occ, used):
	cnt = [0] * 20
	cnt[0] = 1
	for (digit, rep) in enumerate(occ):
		if cnt == 0 or rep == 0:
			continue
		res = [0] * 20
		r = range(rep + 1) if digit == used else range(1, rep + 1)
		for i in r:
			for (j, x) in enumerate(cnt):
				if i + j >= 20:
					continue
				res[i + j] += x * newt(j + i, i)
		cnt = res
	return sum(cnt)
n = input()
occ = [n.count(str(x)) for x in range(10)]
ans = 0
for i in range(1, 10):
	if occ[i] > 0:
		occ[i] -= 1
		ans += go(occ, i)
		occ[i] += 1
print(ans)


from itertools import chain, combinations
from collections import defaultdict
import math

def powerset(iterable):
	xs = iterable
	return chain.from_iterable((combinations(xs, n) for n in range(1, len(xs) + 1)))

def has(s):
	h = 1
	p = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
	for i in s:
		h *= p[i - 1]
	return h
h = set()
total = 0
inp = input().strip()
if int(inp) == 1000000000000000000:
	print(18)
else:
	ok = [int(i) for i in inp]
	require = set(ok)
	for s in powerset(ok):
		if has(s) in h:
			continue
		h.add(has(s))
		d = defaultdict(int)
		prod = 1
		for c in s:
			d[c] += 1
			prod *= d[c]
		flag = False
		for i in require:
			if d[i] == 0:
				flag = True
				break
		if flag:
			continue
		n = len(s)
		total += (n - d[0]) * math.factorial(n - 1) / prod
	print(int(total))


from math import factorial
n = input()
k = len(n)
digits = set(map(int, set((c for c in n))))
seen = set()
char_count = [0 for _ in range(10)]

def split(s):
	global char_count
	for _ in range(10):
		char_count[_] = 0
	for c in s:
		char_count[ord(c) - 48] += 1

def get_count():
	global char_count
	ans = factorial(sum(char_count))
	for c in char_count:
		ans /= factorial(c)
	return ans

def get_ans(s):
	global seen, char_count, digits
	split(s)
	if not all((char_count[d] for d in digits)):
		return 0
	s = ''.join(sorted(s))
	if s in seen:
		return 0
	seen.add(s)
	ans = get_count()
	if char_count[0] > 0:
		char_count[0] -= 1
		ans -= get_count()
	return ans
total = 0
for i in range(1, 1 << k + 1):
	c = ''
	c2 = ''
	for j in range(k):
		if i & 1 << j:
			c += n[j]
	total += get_ans(c)
print(int(total))


import math
n = int(input())
s = str(n)
di = {}
for c in list(s):
	if c in di:
		di[c] += 1
	else:
		di[c] = 1
d = {}
v = [k for k in di]
cnt = {k: 1 for k in di}
ans = 0

def solve():
	n = len(v)
	r = 0
	if '0' in cnt:
		r = cnt['0']
	ans = n - r
	for i in range(1, n):
		ans = ans * (n - i)
	for k in cnt:
		ans = ans / math.factorial(cnt[k])
	return ans

def f(index):
	global ans
	ans += solve()
	for (ind, k) in enumerate(di):
		if ind < index:
			continue
		if cnt[k] < di[k]:
			v.append(k)
			cnt[k] += 1
			f(ind)
			v.pop()
			cnt[k] -= 1
f(0)
print(int(ans))


import itertools

def permutation(arr):
	ret = []
	pos = -1
	flag = 0
	c = arr.copy()
	for i in range(10):
		if c[i] > 1:
			c[i] -= 1
			pos = i
			flag = 1
			break
	if flag == 1:
		for num in permutation(c):
			p = num.copy()
			ret.append(num)
			p[pos] += 1
			ret.append(p)
		return ret
	else:
		return [c]
n = input()
arr = [0 for i in range(10)]
for i in range(len(n)):
	arr[int(n[i])] += 1
k = permutation(arr)
k.sort()
lis = list((k for (k, _) in itertools.groupby(k)))
fac = [1] * 20
for i in range(2, 20):
	fac[i] *= i * fac[i - 1]
ans = 0
for elem in lis:
	temp = fac[sum(elem) - 1] * (sum(elem) - elem[0])
	for i in elem:
		temp = temp // fac[i]
	ans += temp
print(ans)


from collections import Counter
from math import factorial as f

def main():
	cnt = Counter(input())
	le = sum(cnt.values())
	nxt = {0: f(le)}
	for (d, v) in cnt.items():
		(cur, nxt) = (nxt, Counter())
		for (i, u) in cur.items():
			for j in range(v, 0, -1):
				nxt[i + j] += u // f(j)
				if d == '0':
					nxt[i + j - 1] -= u // f(j - 1)
	res = 0
	for (i, u) in nxt.items():
		for j in range(le, i, -1):
			u //= j
		res += u
	print(res)
main()


from math import factorial as f
from functools import reduce as d
from operator import mul as m
from itertools import product as p
(u, t, r, s) = (map, sum, range, input())
print(t((f(t(x)) // d(m, u(f, x)) - f(t(x) - 1) * x[0] // d(m, u(f, x)) * (x[0] > 0) for x in p(*[r(y and 1, y + 1) for y in [s.count(str(d)) for d in r(10)]]))))


n = int(input())
num = []
tmp = []
a = []
F = []
res = 0
F.append(1)
for i in range(1, 20):
	F.append(F[i - 1] * i)

def cal(cnt, flag):
	amo = 0
	ret = 1
	for i in a:
		ret *= F[i]
		amo += i
	ret = F[amo] // ret
	if flag:
		a[0] -= 1
		ret -= cal(cnt, False)
		a[0] += 1
	return ret

def dfs(now, cnt, flag):
	if now == cnt:
		return cal(cnt, flag)
	ret = 0
	for i in range(1, tmp[now] + 1):
		a[now] = i
		ret += dfs(now + 1, cnt, flag)
	return ret
for i in range(0, 10):
	num.append(0)
while n > 0:
	num[n % 10] += 1
	n //= 10
for i in num:
	if i > 0:
		tmp.append(i)
cnt = len(tmp)
for i in range(0, cnt):
	a.append(0)
flag = bool(num[0] > 0)
print(dfs(0, cnt, flag))


n = input()
facts = {0: 1}

def fact(a):
	nonlocal facts
	if a in facts:
		return facts[a]
	res = 1
	for i in range(1, a + 1):
		res *= i
		facts[i] = res
	return facts[a]
occ = [0] * 10
for i in range(len(n)):
	occ[int(n[i])] += 1
ans = 0

def go_find(hame, start):
	nonlocal ans
	if hame[0] == 0:
		res = fact(sum(hame))
		for i in range(10):
			res //= fact(hame[i])
	else:
		res2 = fact(sum(hame) - 1)
		for i in range(1, 10):
			res2 //= fact(hame[i])
		res2 //= fact(hame[0] - 1)
		res = fact(sum(hame))
		for i in range(10):
			res //= fact(hame[i])
		res -= res2
	ans += res
	for i in range(start, 10):
		if hame[i] > 1:
			hame[i] -= 1
			go_find(hame, i)
			hame[i] += 1
go_find(occ, 0)
print(ans)


ct = [0] * 10
fact = [1] * 20
ans = 0

def setAns(lol):
	nonlocal ans
	ans = lol

def calc(k, fr):
	if k == 10:
		tot = sum(fr)
		w0 = fact[tot]
		for i in range(10):
			w0 //= fact[fr[i]]
		wo0 = 0
		if fr[0] > 0:
			fr[0] -= 1
			wo0 = fact[tot - 1]
			for i in range(10):
				wo0 //= fact[fr[i]]
			fr[0] += 1
		tp = w0 - wo0
		setAns(ans + tp)
		return
	if ct[k] == 0:
		calc(k + 1, fr)
		return
	for i in range(1, ct[k] + 1):
		fr[k] = i
		calc(k + 1, fr)
fact[0] = 1
for i in range(1, 20):
	fact[i] = fact[i - 1] * i
n = int(input())
while n > 0:
	k = n % 10
	n //= 10
	ct[k] += 1
freq = [0] * 10
calc(0, freq)
print(ans)


n = input()
rg = [0] * 10
for i in n:
	rg[int(i)] += 1
rl = []
ff = 0
for i in range(len(rg)):
	if rg[i] != 0:
		rl.append(rg[i])
		if i == 0:
			ff = 1
fact = [1]
fc = 1
for i in range(1, 20):
	fc *= i
	fact.append(fc)
rt = []
t = 0

def cfs(d):
	if d == len(rl):
		nonlocal t, ff
		jj = fact[sum(rt)]
		for i in rt:
			jj = jj / fact[i]
		if ff:
			jjj = fact[sum(rt) - 1]
			jjj = jjj / fact[rt[0] - 1]
			for i in range(1, len(rt)):
				jjj = jjj / fact[rt[i]]
			jj -= jjj
		t += jj
		return
	for i in range(1, rl[d] + 1):
		rt.append(i)
		cfs(d + 1)
		rt.pop(-1)
cfs(0)
print(int(t))


def faktorijel(num):
	if num == 0:
		return 1
	x = 1
	for i in range(1, num + 1):
		x *= i
	return x
n = list(input())
znams = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
for i in n:
	znams[int(i)] += 1
broj = 0
for broj0 in range(min(znams[0], 1), max(1, znams[0] + 1)):
	for broj1 in range(min(znams[1], 1), max(1, znams[1] + 1)):
		for broj2 in range(min(znams[2], 1), max(1, znams[2] + 1)):
			for broj3 in range(min(znams[3], 1), max(1, znams[3] + 1)):
				for broj4 in range(min(znams[4], 1), max(1, znams[4] + 1)):
					for broj5 in range(min(znams[5], 1), max(1, znams[5] + 1)):
						for broj6 in range(min(znams[6], 1), max(1, znams[6] + 1)):
							for broj7 in range(min(znams[7], 1), max(1, znams[7] + 1)):
								for broj8 in range(min(znams[8], 1), max(1, znams[8] + 1)):
									for broj9 in range(min(znams[9], 1), max(1, znams[9] + 1)):
										y = faktorijel(broj0 + broj1 + broj2 + broj3 + broj4 + broj5 + broj6 + broj7 + broj8 + broj9) / (faktorijel(broj0) * faktorijel(broj1) * faktorijel(broj2) * faktorijel(broj3) * faktorijel(broj4) * faktorijel(broj5) * faktorijel(broj6) * faktorijel(broj7) * faktorijel(broj8) * faktorijel(broj9))
										broj += y
										if broj0 != 0:
											x = faktorijel(broj0 - 1 + broj1 + broj2 + broj3 + broj4 + broj5 + broj6 + broj7 + broj8 + broj9) / (faktorijel(broj0 - 1) * faktorijel(broj1) * faktorijel(broj2) * faktorijel(broj3) * faktorijel(broj4) * faktorijel(broj5) * faktorijel(broj6) * faktorijel(broj7) * faktorijel(broj8) * faktorijel(broj9))
											broj += -x
print(int(broj))


n = input()
cnt = [0] * 10
for d in n:
	cnt[int(d)] += 1
m = [0] * 10
ans = 0

def DFS(i: int):
	global ans
	if i == 10:
		pans = 1
		for j in range(sum(m)):
			pans *= j + 1
		for j in range(10):
			for k in range(m[j]):
				pans //= k + 1
		ans += pans
		if m[0]:
			pans = 1
			for j in range(1, sum(m)):
				pans *= j
			for j in range(10):
				for k in range(m[j] - (j == 0)):
					pans //= k + 1
			ans -= pans
	elif cnt[i] == 0:
		DFS(i + 1)
	else:
		for j in range(0, cnt[i]):
			m[i] = j + 1
			DFS(i + 1)
DFS(0)
print(ans)


import sys
S = sys.stdin.read()
S = int(S)

def fac(x):
	if x < 2:
		return 1
	return x * fac(x - 1)

def mult(L):
	i = 1
	for j in L:
		i *= j
	return i

def comb(n, k):
	return fac(n + k) / fac(n) / fac(k)
E = [0 for x in '0123456789']
F = [0 for x in E]
for i in str(S):
	E[int(i)] += 1
R = 0

def Find(D, k):
	global R
	r = fac(sum(D)) / mult(list(map(fac, D)))
	if D[0] > 0:
		r -= r * D[0] / sum(D)
	if k < 0:
		for i in range(len(D)):
			if not D[i] and E[i]:
				return
		R += r
	else:
		for i in range(E[k] + 1):
			D[k] = i
			Find(D, k - 1)
for i in range(E[-1] + 1):
	F[-1] = i
	Find(F, 8)
print(int(R))


def fact(n):
	global fa
	if fa[n] != -1:
		return fa[n]
	else:
		fa[n] = fact(n - 1) * n
		return fa[n]
fa = [-1] * 20
fa[0] = 1
fa[1] = 1
fa[2] = 2
res = 0
a = int(input())
b = str(a)
s = [0] * 10
for i in range(len(b)):
	s[int(b[i])] += 1
for i0 in range(s[0] + 1):
	if i0 > 0 or s[0] == 0:
		for i1 in range(s[1] + 1):
			if i1 > 0 or s[1] == 0:
				for i2 in range(s[2] + 1):
					if i2 > 0 or s[2] == 0:
						for i3 in range(s[3] + 1):
							if i3 > 0 or s[3] == 0:
								for i4 in range(s[4] + 1):
									if i4 > 0 or s[4] == 0:
										for i5 in range(s[5] + 1):
											if i5 > 0 or s[5] == 0:
												for i6 in range(s[6] + 1):
													if i6 > 0 or s[6] == 0:
														for i7 in range(s[7] + 1):
															if i7 > 0 or s[7] == 0:
																for i8 in range(s[8] + 1):
																	if i8 > 0 or s[8] == 0:
																		for i9 in range(s[9] + 1):
																			if i9 > 0 or s[9] == 0:
																				w2 = [i0, i1, i2, i3, i4, i5, i6, i7, i8, i9]
																				su = 0
																				for i in range(10):
																					su += w2[i]
																				for i in range(1, 10):
																					if w2[i] > 0:
																						w2[i] -= 1
																						su -= 1
																						res += fact(su) / (fact(w2[0]) * fact(w2[1]) * fact(w2[2]) * fact(w2[3]) * fact(w2[4]) * fact(w2[5]) * fact(w2[6]) * fact(w2[7]) * fact(w2[8]) * fact(w2[9]))
																						su += 1
																						w2[i] += 1
print(int(res))


import time
import math

def test(num, a, step):
	if step == 10:
		s = sum(a)
		ans = s - a[0]
		s -= 1
		ans *= math.factorial(s)
		for i in a:
			if i != 0:
				ans /= math.factorial(i)
		return int(ans)
	if num[step] == 0:
		return test(num, a, step + 1)
	ans = 0
	a[step] = 0
	for i in range(num[step]):
		a[step] += 1
		ans += test(num, a, step + 1)
	return ans
n = [int(i) for i in input()]
start = time.time()
num = [0 for i in range(10)]
for i in n:
	num[i] += 1
a = [0 for i in range(10)]
ans = test(num, a, 0)
print(ans)
finish = time.time()


a = map(int, input())
cnts = [0] * 10
for aa in a:
	cnts[aa] += 1
mem = {}
mem[1, 0, 0, 0, 0, 0, 0, 0, 0, 0] = 0
for i in range(1, 10):
	mem[(0,) * i + (1,) + (0,) * (10 - i - 1)] = 1

def get(a):
	if tuple(a) in mem:
		return mem[tuple(a)]
	else:
		aa = list(a)
		tot = 0
		for i in range(0, 10):
			if a[i] != 0:
				aa[i] -= 1
				tot += get(aa)
				aa[i] += 1
		mem[tuple(a)] = tot
		return tot
bigTot = 0

def goThrough(pre, post):
	global bigTot
	if len(post) == 0:
		bigTot += get(pre)
	elif post[0] == 0:
		goThrough(pre + (0,), post[1:])
	else:
		for i in range(1, post[0] + 1):
			goThrough(pre + (i,), post[1:])
goThrough((), cnts)
print(bigTot)


from collections import defaultdict
from copy import deepcopy
a = list(input())
d = defaultdict(int)
for x in a:
	d[int(x)] += 1
fact_mem = {}

def fact(n):
	if n in fact_mem:
		return fact_mem[n]
	ans = 1
	for i in range(1, n + 1):
		ans *= i
	fact_mem[n] = ans
	return ans
mem = {}

def f(d):
	tmp = frozenset(d.items())
	if tmp in mem:
		return 0
	n = sum(d.values())
	ans = 0
	if d[0] > 0:
		ans += (n - d[0]) * fact(n - 1)
	else:
		ans += fact(n)
	if len(d) == 1 and d[0] > 0:
		return 0
	for x in d:
		ans //= fact(d[x])
	for k in d:
		if d[k] > 1:
			e = deepcopy(d)
			e[k] -= 1
			ans += f(e)
	mem[frozenset(d.items())] = ans
	return ans
ans = f(d)
print(ans)


n = int(input())
s = str(n)
ans = 0
a = [s.count(str(digit)) for digit in range(10)]
from math import factorial
from functools import reduce
from operator import mul

def get(*args):
	res = factorial(sum(args))
	for x in args:
		res //= factorial(x)
	return res
for a0 in range(0 if not a[0] else 1, a[0] + 1):
	for a1 in range(0 if not a[1] else 1, a[1] + 1):
		for a2 in range(0 if not a[2] else 1, a[2] + 1):
			for a3 in range(0 if not a[3] else 1, a[3] + 1):
				for a4 in range(0 if not a[4] else 1, a[4] + 1):
					for a5 in range(0 if not a[5] else 1, a[5] + 1):
						for a6 in range(0 if not a[6] else 1, a[6] + 1):
							for a7 in range(0 if not a[7] else 1, a[7] + 1):
								for a8 in range(0 if not a[8] else 1, a[8] + 1):
									for a9 in range(0 if not a[9] else 1, a[9] + 1):
										ans += get(a0, a1, a2, a3, a4, a5, a6, a7, a8, a9)
										if a0:
											ans -= get(a0 - 1, a1, a2, a3, a4, a5, a6, a7, a8, a9)
print(ans)


n = input()
hsh = [0] * 10
for i in n:
	hsh[ord(i) - ord('0')] += 1

def f(n):
	if n < 2:
		return 1
	else:
		return n * f(n - 1)
ans = 0
sea = []

def rec(table):
	val = int(''.join(list(map(str, table))))
	if val not in sea:
		global ans
		s = 1
		t = sum(table)
		for i in range(10):
			s *= f(table[i])
		minus = 1
		if table[0] > 0:
			table[0] -= 1
			for i in range(10):
				minus *= f(table[i])
			ans += f(t) // s - f(t - 1) // minus
			table[0] += 1
		else:
			ans += f(t) // s
		sea.append(val)
		for i in range(10):
			if table[i] > 1:
				table[i] -= 1
				rec(table)
				table[i] += 1
rec(hsh)
print(ans)


from math import *
from collections import defaultdict

def ncr(n, r):
	p = 1
	k = 1
	if n - r < r:
		r = n - r
	if r != 0:
		while r:
			p *= n
			k *= r
			m = gcd(p, k)
			p //= m
			k //= m
			n -= 1
			r -= 1
	else:
		p = 1
	return p
from sys import stdin
from math import log, ceil
dic = defaultdict(str)
t = 1

def fun(l, length):
	if set(l[1:]) == set([0]):
		return 0
	if length == 1:
		return 1
	s = ''
	for i in l:
		s += str(i)
	if dic[s] == 1:
		return 0
	dic[s] = 1
	ans1 = factorial(length)
	temp = factorial(length - 1)
	for i in range(10):
		if l[i] > 0:
			ans1 /= factorial(l[i])
			if i == 0:
				temp /= factorial(max(1, l[i] - 1))
			else:
				temp /= factorial(l[i])
	if l[0] > 0:
		ans1 = ans1 - temp
	for i in range(10):
		if l[i] > 1:
			l1 = l[:]
			l1[i] -= 1
			ans1 += fun(l1, length - 1)
	return ans1
ans = 0
for _ in range(t):
	n = list(input())
	l = [0] * 10
	for i in n:
		l[int(i)] += 1
	print(int(fun(l, len(n))))


import sys
sys.setrecursionlimit(10 ** 5)
n = str(input())
C = [0] * 10
for c in n:
	C[int(c)] += 1
import copy
memo = {}

def dfs(state):
	res = 0
	if tuple(state) in memo:
		return memo[tuple(state)]
	for i in range(10):
		if C[i] != 0 and state[i] == 0:
			break
	else:
		res += 1
	for i in range(10):
		if C[i] - state[i] >= 1:
			state[i] += 1
			res += dfs(state)
			state[i] -= 1
	memo[tuple(state)] = res
	return res
ans = 0
for i in range(1, 10):
	if C[i] >= 1:
		state = [0] * 10
		state[i] += 1
		ans += dfs(state)
print(ans)


s = input()
cnt = [0 for i in range(10)]
for c in s:
	cnt[ord(c) - ord('0')] += 1
dp = [0 for i in range(20)]
dp[0] = 1
comb = [[0 for i in range(40)] for j in range(40)]
for i in range(40):
	for j in range(i + 1):
		if i == j or j == 0:
			comb[i][j] = 1
		else:
			comb[i][j] = comb[i - 1][j] + comb[i - 1][j - 1]
for dig in [1, 2, 3, 4, 5, 6, 7, 8, 9, 0]:
	if cnt[dig] == 0:
		continue
	odp = dp
	dp = [0] * 20
	for lsz in range(20):
		for pick in range(1, cnt[dig] + 1):
			if lsz + pick < 20:
				m = lsz + (dig != 0) + pick - 1
				r = lsz + (dig != 0) - 1
				ways = 0
				if m == r:
					ways = 1
				elif r > m or r < 0 or m < 0:
					ways = 0
				else:
					ways = comb[m][r]
				dp[lsz + pick] += odp[lsz] * ways
res = 0
for i in range(1, 20):
	res += dp[i]
print(res)


def enc(t):
	v = 0
	for x in t:
		v *= 20
		v += x
	return v

def dec(v, N):
	a = []
	for _ in range(N):
		a.append(v % 20)
		v //= 20
	a.reverse()
	return a

def cnt(C, ld, ud):
	N = len(C)
	ans = 0
	dp = {enc([0] * N): 1}
	for rnd in range(ud):
		if rnd >= ld:
			for et in dp:
				c = dp[et]
				t = dec(et, N)
				if C[0] == 0 and all([t[i] >= 1 for i in range(1, N)]) or (C[0] > 0 and all([t[i] >= 1 for i in range(N)])):
					ans += c
		ndp = {}
		for et in dp:
			t = dec(et, N)
			c = dp[et]
			for i in range(N):
				if rnd == 0 and i == 0:
					continue
				if t[i] < C[i]:
					l = list(t)
					l[i] += 1
					nt = enc(l)
					if nt not in ndp:
						ndp[nt] = 0
					ndp[nt] += c
		dp = ndp
	for et in dp:
		c = dp[et]
		t = dec(et, N)
		if C[0] == 0 and all([t[i] >= 1 for i in range(1, N)]) or (C[0] > 0 and all([t[i] >= 1 for i in range(N)])):
			ans += c
	return ans

def solve(S):
	N = len(S)
	C = [0] * 10
	for c in S:
		C[ord(c) - ord('0')] += 1
	mindigits = len([c for c in C if c > 0])
	C = [C[0]] + [C[i] for i in range(1, 10) if C[i] > 0]
	return cnt(C, mindigits, N)

def main():
	S = input()
	print(solve(S))
main()


import itertools
from collections import defaultdict
n = input()
digits = [0] * 10
for i in n:
	digits[int(i)] += 1

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

def nchoosek(n, k):
	k = max([k, n - k])
	ans = 1
	for i in range(k + 1, n + 1):
		ans *= i
	ans //= fact(n - k)
	return ans
ans = 0
for amounts in itertools.product(*[[0] if x == 0 else range(1, x + 1) for x in digits]):
	not_zero = sum(amounts[1:])
	if not_zero == 0:
		continue
	tmp = fact(not_zero)
	for j in amounts[1:]:
		tmp //= fact(j)
	tmp *= nchoosek(not_zero - 1 + amounts[0], amounts[0])
	ans += tmp
print(ans)


from collections import defaultdict as dd
from math import factorial as f
s = input()
cnt = dd(int)
for i in s:
	cnt[i] += 1
ans = 0

def calc(cur_chr, dem, do_not_take_sum, total, diff):
	nonlocal ans
	nonlocal cnt
	if cur_chr == '9':
		for do_not_take in range(0, cnt[cur_chr] + 1):
			if do_not_take > 0 and do_not_take == cnt[cur_chr]:
				continue
			cur_do_not_take_sum = do_not_take_sum + do_not_take
			if cur_do_not_take_sum == total:
				continue
			cur_dem = dem * f(cnt[cur_chr] - do_not_take)
			num = f(total - cur_do_not_take_sum)
			ans += num // cur_dem * diff
		return
	for do_not_take in range(0, cnt[cur_chr] + 1):
		if do_not_take > 0 and do_not_take == cnt[cur_chr]:
			if not (diff == -1 and cur_chr == '0'):
				continue
		calc(chr(ord(cur_chr) + 1), dem * f(cnt[cur_chr] - do_not_take), do_not_take_sum + do_not_take, total, diff)
calc('0', 1, 0, len(s), 1)
if cnt['0'] != 0:
	cnt['0'] -= 1
	calc('0', 1, 0, len(s) - 1, -1)
print(ans)


import sys
import math
from collections import defaultdict
ans = 0

def get(dic, cur, size, ans, arr, vis):
	if vis[tuple(arr)] == 1:
		return 0
	vis[tuple(arr)] = 1
	res = fac[size]
	for i in cur:
		res //= fac[cur[i]]
	if cur['0'] > 0:
		y = fac[size - 1]
		for i in cur:
			if i != '0':
				y //= fac[cur[i]]
			else:
				y //= fac[cur[i] - 1]
		res -= y
	ans += res
	res2 = 0
	for j in dic:
		if dic[j] >= 1:
			temp = cur.copy()
			temp[j] += 1
			dictemp = dic.copy()
			dictemp[j] -= 1
			arr[int(j)] -= 1
			x = get(dictemp, temp, size + 1, ans, arr, vis)
			arr[int(j)] += 1
			res2 += x
	return res + res2
s = sys.stdin.readline()[:-1]
fac = [1]
for i in range(1, 30):
	x = fac[-1] * i
	fac.append(x)
dic = defaultdict(int)
n = len(s)
arr = [0 for _ in range(10)]
for i in range(n):
	dic[s[i]] += 1
	arr[int(s[i])] += 1
cur = defaultdict(int)
for i in dic:
	dic[i] -= 1
	cur[i] += 1
	arr[int(i)] -= 1
vis = defaultdict(int)
x = get(dic, cur, len(dic), ans, arr, vis)
print(x)


from itertools import product
from operator import mul
from functools import reduce
n = input().strip()
c0 = n.count('0')
cc = [n.count(str(i)) for i in range(10)]
cc = [c for c in cc if c > 0]
facs = [1]
for i in range(1, 20):
	facs.append(facs[-1] * i)

def prod(p):
	return reduce(mul, p, 1)

def getC(p):
	return facs[sum(p)] // prod((facs[pp] for pp in p))

def getcount(ct, a0=False):
	its = [range(1 - int(a0), ct[0] + 1)] + [range(1, cti + 1) for cti in ct[1:]]
	return sum((getC(p) for p in product(*its)))
if c0 == 0:
	res = getcount(cc)
elif c0 == 1:
	ccr = list(cc)
	del ccr[0]
	res = getcount(cc) - getcount(ccr)
else:
	ccr = list(cc)
	ccr[0] -= 1
	res = getcount(cc) - getcount(ccr, True)
print(res)


from math import factorial as fac

def generate_poslist(lis, length):
	if length == 0:
		return [[]]
	elems = lis[0]
	temp = lis.pop(0)
	recval = generate_poslist(lis, length - 1)
	ansl = []
	for anyl in recval:
		ansl.extend(list(map(lambda x: [x] + anyl, elems)))
	return ansl

def getsum(l):
	sumfac = fac(sum(l))
	prod = 1
	for e in l:
		prod = prod * fac(e)
	return sumfac / prod
wnum = input('')
digdic = dict()
for dig in wnum:
	digdic[dig] = digdic.get(dig, 0) + 1
baselist = []
for (key, val) in digdic.items():
	baselist.append(list(range(1, val + 1)))
possibility_list = generate_poslist(baselist, len(baselist))
sum1 = 0
sum2 = 0
for lis in possibility_list:
	sum1 += getsum(lis)
forzero = digdic.get('0', 0)
if forzero != 0:
	if forzero == 1:
		del digdic['0']
	else:
		digdic['0'] = forzero - 1
	baselist = []
	for (key, val) in digdic.items():
		if key == '0':
			baselist.append(list(range(0, val + 1)))
			continue
		baselist.append(list(range(1, val + 1)))
	possibility_list = generate_poslist(baselist, len(baselist))
	for lis in possibility_list:
		sum2 += getsum(lis)
print(int(sum1 - sum2))


fact = [0 for _ in range(35)]
fact[0] = 1
for q in range(1, 35):
	fact[q] = fact[q - 1] * q
amts = []
ans = 0

def multinom():
	tot = 0
	for i in amts:
		tot = tot + i
	ret = fact[tot]
	for i in amts:
		ret = ret / fact[i]
	return ret
t = int(input())
digct = []
for i in range(10):
	digct.append(0)
tcpy = t
while tcpy > 0:
	digct[int(tcpy % 10)] = digct[int(tcpy % 10)] + 1
	tcpy = tcpy // 10

def dfs(place):
	global ans
	if place == 10:
		ans = ans + multinom()
		if amts[0] > 0:
			amts[0] = amts[0] - 1
			ans = ans - multinom()
			amts[0] = amts[0] + 1
		return
	if digct[place] == 0:
		amts.append(0)
		dfs(place + 1)
		amts.pop()
	else:
		for q in range(1, digct[place] + 1):
			amts.append(q)
			dfs(place + 1)
			amts.pop()
dfs(0)
print(int(ans))


factorial_array = [1]
for x in range(1, 20):
	factorial_array.append(factorial_array[-1] * x)

def factorial(x):
	global factorial_array
	return factorial_array[x]

def generate(array):
	start = factorial(sum(array))
	for x in range(10):
		start //= factorial(array[x])
	return start

def main():
	string = input()
	store = [0 for x in range(10)]
	for x in range(len(string)):
		store[int(string[x])] += 1
	all_possible = [[]]
	for x in range(10):
		next_all_possible = []
		for y in all_possible:
			if store[x] == 0:
				next_all_possible.append(y + [0])
			else:
				for z in range(1, store[x] + 1):
					next_all_possible.append(y + [z])
		all_possible = next_all_possible.copy()
	total = 0
	for x in all_possible:
		total += generate(x)
		if x[0] > 0:
			x[0] -= 1
			total -= generate(x)
	print(total)
main()


n = input()
all = [0] * 10
for x in n:
	all[int(x)] += 1
dp = [0] * 20
dp[0] = 1
for i in range(1, 10):
	cur = [0] * 20
	if all[i] > 0:
		for le in range(0, 20):
			fac = 1
			zn = 1
			for kol in range(1, all[i] + 1):
				if le + kol < 20:
					zn *= le + kol
					fac *= kol
					cur[le + kol] += zn // fac * dp[le]
		dp = cur
cur = [0] * 20
if all[0] > 0:
	for le in range(1, 20):
		fac = 1
		zn = 1
		for kol in range(1, all[0] + 1):
			if le + kol < 20:
				zn *= le + kol - 1
				fac *= kol
				cur[le + kol] += zn // fac * dp[le]
	dp = cur
print(sum(dp))


n = int(input())
t = []
a = []
for i in range(10):
	t.append(0)
	a.append(1)
while n:
	a[n % 10] += 1
	n //= 10
ans = 0
for i in range(a[0] != 1, a[0]):
	t[0] = i
	for i in range(a[1] != 1, a[1]):
		t[1] = i
		for i in range(a[2] != 1, a[2]):
			t[2] = i
			for i in range(a[3] != 1, a[3]):
				t[3] = i
				for i in range(a[4] != 1, a[4]):
					t[4] = i
					for i in range(a[5] != 1, a[5]):
						t[5] = i
						for i in range(a[6] != 1, a[6]):
							t[6] = i
							for i in range(a[7] != 1, a[7]):
								t[7] = i
								for i in range(a[8] != 1, a[8]):
									t[8] = i
									for i in range(a[9] != 1, a[9]):
										t[9] = i
										s = 0
										for i in range(10):
											s += t[i]
										w = 1
										cnt = s
										for i in range(10):
											for j in range(t[i]):
												if i == 0:
													w *= cnt - 1
												else:
													w *= cnt
												cnt -= 1
										for i in range(10):
											for j in range(1, t[i] + 1):
												w //= j
										ans += w
print(ans)


f = [1]
for i in range(1, 50):
	f.append(f[-1] * i)

def c(l):
	ans = f[sum(l)]
	for _ in l:
		ans //= f[_]
	return ans
a = []

def get_sub_add_sub_set(dc, ans):
	if dc == []:
		a.append(ans)
		return
	if dc[0] == 0:
		get_sub_add_sub_set(dc[1:], ans + [0])
		return
	for i in range(1, dc[0] + 1):
		get_sub_add_sub_set(dc[1:], ans + [i])
n = input()
dc = [n.count(str(i)) for i in range(10)]
get_sub_add_sub_set(dc, [])
ans = 0
if dc[0] == 0:
	for _ in a:
		ans += c(_)
else:
	for _ in a:
		ans += c(_)
		_[0] -= 1
		ans -= c(_)
print(ans)


import itertools as it

def factorial(n):
	i = 1
	for j in range(1, n + 1):
		i *= j
	return i

def C(n, k):
	k = max([k, n - k])
	result = 1
	for i in range(k + 1, n + 1):
		result *= i
	result //= factorial(n - k)
	return result
n = input()
digits = [0 for _ in range(10)]
for i in n:
	digits[int(i)] += 1
result = 0
for amounts in it.product(*[[0] if x == 0 else range(1, x + 1) for x in digits]):
	sum_no_zero = sum(amounts[1:])
	if sum_no_zero == 0:
		continue
	tmp = factorial(sum_no_zero)
	for j in amounts[1:]:
		tmp //= factorial(j)
	tmp *= C(sum_no_zero + amounts[0] - 1, amounts[0])
	result += tmp
print(result)


import math
import heapq, bisect
import sys
from collections import deque, defaultdict
from fractions import Fraction
mod = 10 ** 9 + 7
mod1 = 998244353
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class TreeNode:

	def __init__(self, k, v):
		self.key = k
		self.value = v
		self.left = None
		self.right = None
		self.parent = None
		self.height = 1
		self.num_left = 1
		self.num_total = 1

class AvlTree:

	def __init__(self):
		self._tree = None

	def add(self, k, v):
		if not self._tree:
			self._tree = TreeNode(k, v)
			return
		node = self._add(k, v)
		if node:
			self._rebalance(node)

	def _add(self, k, v):
		node = self._tree
		while node:
			if k < node.key:
				if node.left:
					node = node.left
				else:
					node.left = TreeNode(k, v)
					node.left.parent = node
					return node.left
			elif node.key < k:
				if node.right:
					node = node.right
				else:
					node.right = TreeNode(k, v)
					node.right.parent = node
					return node.right
			else:
				node.value = v
				return

	@staticmethod
	def get_height(x):
		return x.height if x else 0

	@staticmethod
	def get_num_total(x):
		return x.num_total if x else 0

	def _rebalance(self, node):
		n = node
		while n:
			lh = self.get_height(n.left)
			rh = self.get_height(n.right)
			n.height = max(lh, rh) + 1
			balance_factor = lh - rh
			n.num_total = 1 + self.get_num_total(n.left) + self.get_num_total(n.right)
			n.num_left = 1 + self.get_num_total(n.left)
			if balance_factor > 1:
				if self.get_height(n.left.left) < self.get_height(n.left.right):
					self._rotate_left(n.left)
				self._rotate_right(n)
			elif balance_factor < -1:
				if self.get_height(n.right.right) < self.get_height(n.right.left):
					self._rotate_right(n.right)
				self._rotate_left(n)
			else:
				n = n.parent

	def _remove_one(self, node):
		replacement = node.left or node.right
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = replacement
			else:
				node.parent.right = replacement
			replacement.parent = node.parent
			node.parent = None
		else:
			self._tree = replacement
			replacement.parent = None
		node.left = None
		node.right = None
		node.parent = None
		self._rebalance(replacement)

	def _remove_leaf(self, node):
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = None
			else:
				node.parent.right = None
			self._rebalance(node.parent)
		else:
			self._tree = None
		node.parent = None
		node.left = None
		node.right = None

	def remove(self, k):
		node = self._get_node(k)
		if not node:
			return
		if AvlTree._is_leaf(node):
			self._remove_leaf(node)
			return
		if node.left and node.right:
			nxt = AvlTree._get_next(node)
			node.key = nxt.key
			node.value = nxt.value
			if self._is_leaf(nxt):
				self._remove_leaf(nxt)
			else:
				self._remove_one(nxt)
			self._rebalance(node)
		else:
			self._remove_one(node)

	def get(self, k):
		node = self._get_node(k)
		return node.value if node else -1

	def _get_node(self, k):
		if not self._tree:
			return None
		node = self._tree
		while node:
			if k < node.key:
				node = node.left
			elif node.key < k:
				node = node.right
			else:
				return node
		return None

	def get_at(self, pos):
		x = pos + 1
		node = self._tree
		while node:
			if x < node.num_left:
				node = node.left
			elif node.num_left < x:
				x -= node.num_left
				node = node.right
			else:
				return (node.key, node.value)
		raise IndexError('Out of ranges')

	@staticmethod
	def _is_left(node):
		return node.parent.left and node.parent.left == node

	@staticmethod
	def _is_leaf(node):
		return node.left is None and node.right is None

	def _rotate_right(self, node):
		if not node.parent:
			self._tree = node.left
			node.left.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.left
			node.left.parent = node.parent
		else:
			node.parent.right = node.left
			node.left.parent = node.parent
		bk = node.left.right
		node.left.right = node
		node.parent = node.left
		node.left = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	def _rotate_left(self, node):
		if not node.parent:
			self._tree = node.right
			node.right.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.right
			node.right.parent = node.parent
		else:
			node.parent.right = node.right
			node.right.parent = node.parent
		bk = node.right.left
		node.right.left = node
		node.parent = node.right
		node.right = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	@staticmethod
	def _get_next(node):
		if not node.right:
			return node.parent
		n = node.right
		while n.left:
			n = n.left
		return n
avl = AvlTree()

class SegmentTree1:

	def __init__(self, data, default='z', func=lambda a, b: min(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: a + b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD

def powm(a, n, m):
	if a == 1 or n == 0:
		return 1
	if n % 2 == 0:
		s = powm(a, n // 2, m)
		return s * s % m
	else:
		return a * powm(a, n - 1, m) % m

def sort_list(list1, list2):
	zipped_pairs = zip(list2, list1)
	z = [x for (_, x) in sorted(zipped_pairs)]
	return z

def product(l):
	por = 1
	for i in range(len(l)):
		por *= l[i]
	return por

def binarySearchCount(arr, n, key):
	left = 0
	right = n - 1
	count = 0
	while left <= right:
		mid = int((right + left) / 2)
		if arr[mid] <= key:
			count = mid + 1
			left = mid + 1
		else:
			right = mid - 1
	return count

def countdig(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def countGreater(arr, n, k):
	l = 0
	r = n - 1
	leftGreater = n
	while l <= r:
		m = int(l + (r - l) / 2)
		if arr[m] >= k:
			leftGreater = m
			r = m - 1
		else:
			l = m + 1
	return n - leftGreater
l = []

def fact(t):
	r = 1
	for i in range(1, t + 1):
		r *= i
	return r

def calc(d, t, s, r, ans, k):
	if t == len(l):
		if k > 0:
			ans += fact(s - 1) * (s - k) // r
		else:
			ans += fact(s) // r
		return ans
	for i in range(d[l[t]]):
		if l[t] == 0:
			k = i + 1
		ans = calc(d, t + 1, s + i + 1, r * fact(i + 1), ans, k)
	return ans
n = input()
d = defaultdict(int)
for i in range(len(n)):
	d[int(n[i])] += 1
l = list(d.keys())
ans = calc(d, 0, 0, 1, 0, 0)
print(ans)


def factor(n):
	ans = 1
	for i in range(2, n + 1):
		ans *= i
	return ans
cnt = [0] * 10
ans = 0

def f(cnts):
	global cnt
	global ans
	if len(cnts) == 10:
		lenk = 0
		for i in range(10):
			lenk += cnts[i]
		cur = factor(lenk) * (lenk - cnts[0]) // lenk
		for i in range(10):
			cur = cur // factor(cnts[i])
		ans += cur
	else:
		if cnt[len(cnts)] <= 1:
			cnts.append(cnt[len(cnts)])
			f(cnts)
			cnts.pop()
			return None
		for i in range(1, cnt[len(cnts)] + 1):
			cnts.append(i)
			f(cnts)
			cnts.pop()
n = int(input())
lenk = 0
while n != 0:
	cnt[n % 10] += 1
	n = n // 10
	lenk += 1
maxi = 0
for i in range(10):
	maxi = max(maxi, cnt[i])
f([])
print(ans)


from math import factorial
from functools import lru_cache

@lru_cache()
def choose(n, k):
	return factorial(n) // factorial(n - k) // factorial(k)

def pos(l):
	out = 1
	s = sum(l)
	for i in l:
		out *= choose(s, i)
		s -= i
	return out

@lru_cache()
def doit(l, i):
	if i == len(l):
		return pos(l)
	out = 0
	for j in range(l[i]):
		newl = list(l)
		newl[i] = j + 1
		out += doit(tuple(newl), i + 1)
	return out
n = input()
counts = [n.count(str(i)) for i in set(n)]
out = doit(tuple(counts), 0)
if '0' in n:
	counts2 = [n.count(str(i)) - (i == '0') for i in set(n)]
	counts3 = [n.count(str(i)) for i in set(n) if i != '0']
	out -= doit(tuple(counts2), 0)
	out -= doit(tuple(counts3), 0)
print(out)


from math import factorial as f
from functools import reduce as d
from operator import mul as m
from itertools import product as p
(u, t, r, s) = (map, sum, range, input())
b = lambda x: d(m, u(f, x))
a = [s.count(str(d)) for d in r(10)]
print(t((f(t(x)) // b(x) - (f(t(x) - 1) * x[0] // b(x) if x[0] else 0) for x in p(*[r(1 - (not y), y + 1) for y in a]))))


def ii():
	return int(input())

def mi():
	return map(int, input().split())

def li():
	return list(mi())
fact = [1] * 1000
for i in range(2, 1000):
	fact[i] = fact[i - 1] * i
s = input()
cnt = {}
for d in '0123456789':
	cnt[int(d)] = s.count(d)
ans = 0

def getcnt(p):
	q = [pi for pi in p if pi != 0]
	num = fact[sum(q)]
	den = 1
	for qi in q:
		den *= fact[qi]
	gc = num // den
	if p[0]:
		q = [pi for pi in p if pi != 0]
		q[0] -= 1
		num = fact[sum(q)]
		den = 1
		for qi in q:
			den *= fact[qi]
		gc -= num // den
	return gc

def rec(d, p):
	nonlocal ans
	if d == 10:
		ans += getcnt(p)
		return
	if cnt[d] == 0:
		p[d] = 0
		rec(d + 1, p)
		return
	for c in range(1, cnt[d] + 1):
		p[d] = c
		rec(d + 1, p)
p = [0] * 10
rec(0, p)
print(ans)


n = input()
s = [0 for i in range(10)]
for i in n:
	s[int(i)] += 1
nol = s[0]
del s[0]

def C(n, k):

	def fact(k):
		s = 1
		for i in range(1, k + 1):
			s *= i
		return s
	return fact(n) / (fact(k) * fact(n - k))

def var(nol, koeff):

	def C(n, k):

		def fact(k):
			s = 1
			for i in range(1, k + 1):
				s *= i
			return s
		return fact(n) / (fact(k) * fact(n - k))
	n = 0
	if nol != 0:
		koeff.append(nol)
	for i in koeff:
		n += i
	s = 1
	for k in koeff:
		s *= C(n, k)
		n -= k
	if nol != 0:
		koeff.remove(nol)
		nol -= 1
		koeff.append(nol)
		s2 = 1
		n = 0
		for i in koeff:
			n += i
		for k in koeff:
			s2 *= C(n, k)
			n -= k
		s -= s2
	return s
c = 0
nado = len(s) - s.count(0)
if nol != 0:
	counter = 1
else:
	counter = 0
for nolik in range(nol + 1):
	for c1 in range(s[0] + 1):
		for c2 in range(s[1] + 1):
			for c3 in range(s[2] + 1):
				for c4 in range(s[3] + 1):
					for c5 in range(s[4] + 1):
						for c6 in range(s[5] + 1):
							for c7 in range(s[6] + 1):
								for c8 in range(s[7] + 1):
									for c9 in range(s[8] + 1):
										koeff = [c1, c2, c3, c4, c5, c6, c7, c8, c9]
										while 0 in koeff:
											koeff.remove(0)
										if len(koeff) == nado:
											if counter == 1 and nolik >= 1 or counter == 0:
												c += var(nolik, koeff)
print(int(c))


n = str(input())
k = len(n)
dig = [0 for i in range(10)]
for x in n:
	dig[int(x)] += 1
ans = 0
fact = [1]
for i in range(1, 20):
	fact.append(fact[i - 1] * i)

def foo(i, tot, val, z):
	if i >= 10:
		global ans
		ans += fact[tot] // val
		if z > 0:
			val = val // fact[z]
			val = val * fact[z - 1]
			ans -= fact[tot - 1] // val
		return
	if dig[i] == 0:
		foo(i + 1, tot, val, z)
	for x in range(1, dig[i] + 1):
		if i != 0:
			foo(i + 1, tot + x, val * fact[x], z)
		if i == 0:
			foo(i + 1, tot + x, val * fact[x], x)
foo(0, 0, 1, 0)
print(ans)


a = int(input())
b = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
while a != 0:
	b[a % 10] += 1
	a //= 10
ans = 0

def fact(n):
	f = 1
	for i in range(1, n + 1):
		f *= i
	return f

def f(n, arr):
	nonlocal ans
	if n == 10:
		sum = 0
		for i in range(10):
			sum += arr[i]
		temp = 1
		temp *= sum - arr[0]
		temp *= fact(sum - 1)
		for i in range(10):
			if arr[i] > 1:
				temp //= fact(arr[i])
		ans += temp
	elif b[n] > 0:
		for i in range(1, b[n] + 1):
			temp = arr.copy()
			temp.append(i)
			f(n + 1, temp)
	else:
		arr.append(0)
		f(n + 1, arr)
f(0, [])
print(int(ans))


s = input()
factors = [1, 1]
for i in range(2, 20):
	factors.append(i * factors[-1])
used = set()
total = 0
uniq_numbers = set(s)
s = sorted(s)
for i in range(1, 2 ** len(s)):
	idxs = str(bin(i))[2:]
	idxs = '0' * (len(s) - len(idxs)) + idxs
	number = ''.join([x for (x, y) in zip(s, idxs) if y == '1'])
	if number in used or set(number) != set(uniq_numbers):
		continue
	else:
		used.add(number)
	d = {}
	for el in number:
		if el in d:
			d[el] += 1
		else:
			d[el] = 1
	cnk = factors[len(number)]
	for (key, value) in d.items():
		cnk /= factors[value]
	if '0' in d:
		d['0'] -= 1
		delta = factors[len(number) - 1]
		for (key, value) in d.items():
			delta /= factors[value]
		cnk -= delta
	total += cnk
total = int(total)
print(total)


from math import factorial as f
from itertools import permutations
s = input()
c = [s.count(str(i)) for i in range(10)]
ans = 0
for d0 in range(c[0] != 0, c[0] + 1):
	for d1 in range(c[1] != 0, c[1] + 1):
		for d2 in range(c[2] != 0, c[2] + 1):
			for d3 in range(c[3] != 0, c[3] + 1):
				for d4 in range(c[4] != 0, c[4] + 1):
					for d5 in range(c[5] != 0, c[5] + 1):
						for d6 in range(c[6] != 0, c[6] + 1):
							for d7 in range(c[7] != 0, c[7] + 1):
								for d8 in range(c[8] != 0, c[8] + 1):
									for d9 in range(c[9] != 0, c[9] + 1):
										scnt = [d0, d1, d2, d3, d4, d5, d6, d7, d8, d9]
										li = []
										for i in range(10):
											li += [i] * scnt[i]
										for i in range(1, 10):
											if not scnt[i]:
												continue
											k = scnt[:]
											k[i] -= 1
											x = f(sum(k))
											for j in range(10):
												x //= f(k[j])
											ans += x
print(ans)


from __future__ import print_function
import sys
import math
import os.path
import random
from copy import deepcopy
from functools import reduce
from collections import Counter, ChainMap, defaultdict
from itertools import cycle, chain
from queue import Queue, PriorityQueue
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, nlargest, nsmallest
import bisect
from statistics import mean, mode, median, median_low, median_high
sys.setrecursionlimit(1000000000)

def log(*args, **kwargs):
	print(*args, file=sys.stderr, **kwargs)

def ni():
	return map(int, input().split())

def nio(offset):
	return map(lambda x: int(x) + offset, input().split())

def nia():
	return list(map(int, input().split()))

def toString(aList, sep=' '):
	return sep.join((str(x) for x in aList))

def toMapInvertIndex(aList):
	return {k: v for (v, k) in enumerate(aList)}

def sortId(arr):
	return sorted(range(arr), key=lambda k: arr[k])

def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a
x = input()
gt = [1] * 20
for i in range(1, len(gt)):
	gt[i] = i * gt[i - 1]
count = [0] * 10
for i in x:
	count[ord(i) - ord('0')] += 1
s = 0
select = [0] * 10

def calc2():
	global s
	n = sum(select)
	gs = gt[n]
	for i in range(10):
		gs //= gt[select[i]]
	s += gs

def calc():
	global select
	n = sum(select) - select[0]
	if n > 0:
		for i in range(1, 10):
			if select[i] > 0:
				select[i] -= 1
				calc2()
				select[i] += 1

def find(i):
	global select
	if i > 9:
		calc()
	elif count[i] == 0:
		find(i + 1)
	else:
		for j in range(1, count[i] + 1):
			select[i] = j
			find(i + 1)
find(0)
print(s)


import math
from collections import defaultdict
dp = dict()
fact = dict()

def facto(val):
	if val not in fact.keys():
		fact[val] = math.factorial(val)
	return fact[val]

def hitung(frek, total):
	global dp
	keys = ' '.join((str(x) for x in frek))
	if keys in dp.keys():
		dp[keys] = 0
		return dp[keys]
	ans = 0
	for i in range(1, 10):
		if frek[i] > 0:
			tmp = facto(total) // facto(frek[i] - 1)
			for j in range(0, 10):
				if i != j and frek[j] > 0:
					tmp //= facto(frek[j])
			ans += tmp
	for i in range(0, 10):
		if frek[i] > 1:
			frek[i] -= 1
			ans += hitung(frek, total - 1)
			frek[i] += 1
	dp[keys] = ans
	return ans
n = int(input())
if n < 10:
	print(1)
else:
	tmp = n
	frek = [0 for _ in range(10)]
	total = 0
	while tmp > 0:
		frek[tmp % 10] += 1
		tmp //= 10
		total += 1
	print(hitung(frek, total - 1))


n = int(input())
s = str(n)
a = [s.count(str(digit)) for digit in range(10)]
from math import factorial
from functools import reduce
from operator import mul

def npermutations_with_replacement(*args):
	return factorial(sum(args)) // reduce(mul, map(factorial, args))
from itertools import product
iterables = [range(0 if not x else 1, x + 1) for x in a]
ans = 0
for cnt in product(*iterables):
	ans += npermutations_with_replacement(*cnt)
	if cnt[0]:
		ans -= npermutations_with_replacement(cnt[0] - 1, *cnt[1:])
print(ans)


import math

def get_n_vars_when_amounts_fixed(a):
	t = math.factorial(sum(a[1:]))
	for i in range(1, len(a)):
		t = t // math.factorial(a[i])
	for i in range(a[0]):
		t *= sum(a[1:]) + i
	t //= math.factorial(a[0])
	return t

def gen(a, b, pos):
	if pos == 10:
		return get_n_vars_when_amounts_fixed(b)
	if a[pos] == 0:
		b[pos] = 0
		return gen(a, b, pos + 1)
	ans = 0
	for i in range(1, a[pos] + 1):
		b[pos] = i
		ans += gen(a, b, pos + 1)
	return ans
a = [0] * 10
s = input()
for ch in s:
	a[int(ch)] += 1
b = [0] * 10
ans = gen(a, b, 0)
print(ans)


import collections
from functools import cmp_to_key
import math
import sys

def getIntList():
	return list(map(int, input().split()))
import bisect
try:
	import numpy
	dprint = print
	dprint('debug mode')
except ModuleNotFoundError:

	def dprint(*args, **kwargs):
		pass

def makePair(z):
	return [(z[i], z[i + 1]) for i in range(0, len(z), 2)]
n = input()
ss = set(n)
cc = collections.Counter()
for x in n:
	cc[x] += 1
zz = list(ss)
zz.sort()
n = len(zz)
z1 = [0 for x in range(n)]
res = 0

def memo(func):
	cache = {}

	def wrap(*args):
		if args not in cache:
			cache[args] = func(*args)
		return cache[args]
	return wrap

@memo
def comb(n, k):
	if k == 0:
		return 1
	if n == k:
		return 1
	return comb(n - 1, k - 1) + comb(n - 1, k)

def dfs(g):
	global res
	if g == n:
		total = sum(z1)
		f = 1
		for i in range(n):
			x = z1[i]
			if zz[i] == '0':
				f *= comb(total - 1, x)
			else:
				f *= comb(total, x)
			total -= x
		res += f
		return
	for i in range(1, cc[zz[g]] + 1):
		z1[g] = i
		dfs(g + 1)
dfs(0)
print(res)


n = input().strip()
cnt = [n.count(chr(ord('0') + i)) for i in range(10)]

def fac(n):
	if n <= 1:
		return 1
	return n * fac(n - 1)

def C(x):
	ans = fac(sum(x))
	for v in x:
		ans //= fac(v)
	return ans

def calc(x, c):
	if x == []:
		return C(c)
	if x[0] == 0:
		return calc(x[1:], c)
	ans = 0
	if x[0] < 0:
		for i in range(0, -x[0] + 1):
			ans += calc(x[1:], c + [i])
	else:
		for i in range(1, x[0] + 1):
			ans += calc(x[1:], c + [i])
	return ans
ans = 0
for i in range(1, 10):
	if cnt[i] > 0:
		cnt[i] -= 1
		cnt[i] = -cnt[i]
		ans += calc(cnt, [])
		cnt[i] = -cnt[i]
		cnt[i] += 1
print(ans)


import itertools as it
S = input().strip()
freq = [0 for i in range(10)]
for i in S:
	u = ord(i) - ord('0')
	freq[u] += 1
fac = [1]
for i in range(1, 20):
	fac.append(i * fac[-1])
total = 0
for x in it.product(*(list(range(0 if i == 0 else 1, i + 1)) for i in freq)):
	Q = ''.join((str(i) * x[i] for i in range(10)))
	s = sum(x) - 1
	if s < 0:
		continue
	g = 0
	for d in range(1, 10):
		n = fac[s]
		y = list(x)
		y[d] -= 1
		for k in range(0, 10):
			n //= fac[y[k]]
		g += n
	total += g
print(total)


N = input()
C = [0] * 10
for n in N:
	C[int(n)] += 1
memo = {}

def dfs(i, state):
	key = tuple(state)
	if key in memo:
		return memo[key]
	r = 0
	if all((s == 0 or 1 <= t for (s, t) in zip(C, state))):
		r += 1
	for j in range(10):
		if C[j] - state[j] > 0:
			state[j] += 1
			r += dfs(i + 1, state)
			state[j] -= 1
	memo[key] = r
	return r
state = [0] * 10
ans = 0
for i in range(1, 10):
	if C[i] > 0:
		state[i] += 1
		ans += dfs(1, state)
		state[i] -= 1
print(ans)


n = int(input())
k = len(str(n))
a = []
factorials = [1]
for i in range(1, 20):
	factorials.append(factorials[i - 1] * i)
for i in range(2 ** k):
	s = ''
	for j in range(k):
		if i & 2 ** j != 0:
			s += str(n)[j]
	fl = True
	for j in str(n):
		if j not in s:
			fl = False
			break
	if fl and sorted(list(s)) not in a:
		a.append(sorted(list(s)))
otv = 0
for i in a:
	ans = factorials[len(i)]
	for j in list(set(i)):
		ans //= factorials[i.count(j)]
	if '0' in i:
		del i[i.index('0')]
		ans2 = factorials[len(i)]
		for j in list(set(i)):
			ans2 //= factorials[i.count(j)]
		ans -= ans2
	otv += ans
print(otv)


from sys import stdin
from math import factorial as fac
s = list(stdin.readline().strip())
top = 2 ** len(s)
for i in range(len(s)):
	s[i] = int(s[i])
s.sort()

def can(s1):
	dp = [False for i in range(10)]
	for i in range(len(s1)):
		dp[s1[i]] = True
	for i in s:
		if dp[i] == False:
			return False
	return True

def countf(y):
	d = {0: 0, 1: 0, 2: 0, 3: 0, 4: 0, 5: 0, 6: 0, 7: 0, 8: 0, 9: 0}
	tot = len(y)
	for i in y:
		d[i] += 1
	ans = 0
	a = fac(tot - 1)
	for i in range(1, 10):
		if d[i] > 0:
			b = 1
			for j in range(10):
				if i == j:
					b *= fac(d[j] - 1)
				else:
					b *= fac(d[j])
			ans += a // b
	return ans
r = 0
st = set()
for i in range(1, top):
	x = i
	y = []
	z = 0
	z1 = 0
	for j in range(len(s)):
		if x & 1:
			z1 += s[j] * 10 ** z
			y.append(s[j])
			z += 1
		x >>= 1
	if can(y) and z1 not in st:
		st.add(z1)
		r += countf(y)
print(r)


from itertools import product
from math import factorial
from operator import mul
from functools import reduce
seen = input()
counts = [[0] for digit in range(10)]
for digit in map(int, seen):
	counts[digit].append(counts[digit][-1] + 1)
for digit in range(10):
	if len(counts[digit]) > 1:
		counts[digit].pop(0)
answer = 0
for count in product(*counts):
	answer += factorial(sum(count)) // reduce(mul, (factorial(count[digit]) for digit in range(10)))
	if count[0] > 0:
		count = list(count)
		count[0] -= 1
		answer -= factorial(sum(count)) // reduce(mul, (factorial(count[digit]) for digit in range(10)))
print(answer)