Problem: Example

Input

20


Output

4

Solution (in CPP):

Solution:

#include <bits/stdc++.h>

#define ln                '\n'
#define all(dat)           dat.begin(), dat.end()
#define loop(i, to)        for (int i = 0; i < to; ++i)
#define cont(i, to)        for (int i = 1; i <= to; ++i)
#define circ(i, fr, to)    for (int i = fr; i <= to; ++i)
#define foreach(i, dat)    for (__typeof(dat.begin()) i = dat.begin(); i != dat.end(); ++i)

typedef long long          num;

using namespace std;

const int nsz = 14;
int n;
num k, p = 1, f[nsz + 5] = {1}, dp[nsz + 5][127], ans;
string s;
vector<int> cur, ds, dat;
vector<vector<int>> ps;

void dfs1(int i = 0, int lst = 0, int sum = 0) {
    if (sum > k)  return;
    if (i == n) {
        if (sum == k) {
            num tmp = 1;
            loop (i, cur.size()) {
                tmp *= cur[i] + 1;
            }
            if (tmp < p) {
                num cnt = 1, del = f[n];
                loop (i, cur.size() - 1) {
                    if (cur[i + 1] != cur[i]) {
                        del /= f[cnt];
                        cnt = 0;
                    }
                    ++cnt;
                }
                del /= f[cnt];
                ans += del;
            } else if (tmp == p) {
                ps.push_back(cur);
            }
        }
        return;
    }
    circ (d, lst, 9) {
        cur.push_back(d);
        dfs1(i + 1, d, sum + d);
        cur.pop_back();
    }
}

void dfs2(int me, int id = 0, vector<int> cur = {}) {
    if (id && cur[id - 1] < dat[id - 1]) {
        num cnt = 1, del = f[n - id];
        loop (i, ps[me].size() - 1) {
            if (ps[me][i + 1] != ps[me][i]) {
                del /= f[cnt];
                cnt = 0;
            }
            ++cnt;
        }
        del /= f[cnt];
        ans += del;
        return;
    } else if (id && cur[id - 1] > dat[id - 1])  return;
    if (ps[me].empty())  return;
    loop (i, ps[me].size()) {
        if (i && ps[me][i] == ps[me][i - 1])  continue;
        int tmp = ps[me][i];
        ps[me].erase(ps[me].begin() + i);
        cur.push_back(tmp);
        dfs2(me, id + 1, cur);
        cur.pop_back();
        ps[me].insert(ps[me].begin() + i, tmp);
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin >> s;
    n = (int) s.size();
    cont (i, n) {
        f[i] = f[i - 1] * i;
    }
    loop (i, s.size()) {
        k += s[i] ^ 48;
        p *= (s[i] ^ 48) + 1;
        dat.push_back(s[i] ^ 48);
        ds.push_back(s[i] ^ 48);
    }
    sort(all(ds));
    dp[0][0] = 1;
    loop (i, n) {
        circ (j, 0, i * 9) {
            circ (d, 0, 9) {
                dp[i + 1][j + d] += dp[i][j];
            }
        }
    }
    loop (i, k) {
        ans += dp[n][i];
    }
    dfs1();
    loop (i, ps.size()) {
        dfs2(i);
    }
    cout << ans << ln;
}