Example

Input

20


Output

4

Source: aizu | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
def solve():
	D = input()
	N = len(D)
	(*DI,) = map(int, D)
	su = sum(DI)
	pd = 1
	for d in D:
		pd *= int(d) + 1
	memo = [{} for i in range(N)]

	def dfs0(i, s, p):
		key = (s, p)
		if i == N:
			return s > 0 or (s == 0 and p < pd)
		if key in memo[i]:
			return memo[i][key]
		r = 0
		for v in range(min(s, 9) + 1):
			r += dfs0(i + 1, s - v, p * (v + 1))
		memo[i][key] = r
		return r
	res1 = dfs0(0, su, 1)
	memo1 = [{} for i in range(N)]

	def dfs1(i, s, p, m):
		key = (s, p, m)
		if i == N:
			return s == 0 and p == 1
		if key in memo1[i]:
			return memo1[i][key]
		r = 0
		b = s - (N - 1 - i) * 9
		di = DI[i]
		for v in range(max(b, 0), min(s, 9) + 1):
			if p % (v + 1):
				continue
			if m == 0:
				if di < v:
					break
				r += dfs1(i + 1, s - v, p // (v + 1), +(v < di))
			else:
				r += dfs1(i + 1, s - v, p // (v + 1), 1)
		memo1[i][key] = r
		return r
	res2 = dfs1(0, su, pd, 0) - 1
	ans = res1 + res2
	print(ans)
solve()