p00939 Bringing Order to Disorder
Example

Input

20


Output

4
```python
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()

```