Problem: Example

Input

20


Output

4

Solution (in CPP):

Solution:
#include <iostream>
#include <vector>
#include <string>
#include <map>

using lint = long long;

void solve() {
    std::string t;
    std::cin >> t;

    std::vector<std::vector<std::map<lint, lint>>>
        dp(1, std::vector<std::map<lint, lint>>(3));
    dp[0][1][1] = 1;

    int smax = 0;
    int sum = 0;
    lint prod = 1;
    for (char cc : t) {
        int c = cc - '0';

        sum += c;
        smax += 9;
        prod *= (c + 1);

        std::vector<std::vector<std::map<lint, lint>>>
            ndp(smax + 1, std::vector<std::map<lint, lint>>(3));

        int psmax = dp.size() - 1;
        for (int s = 0; s <= psmax; ++s) {
            for (int k = 0; k <= 2; ++k) {
                for (const auto& q : dp[s][k]) {
                    auto p = q.first;

                    for (int d = 0; d <= 9; ++d) {
                        int ns = s + d;
                        if (ns > smax) continue;

                        lint np = p * (d + 1);
                        int nk = (k != 1 ? k
                                         : (d < c ? 0 : d > c ? 2 : 1));

                        if (!ndp[ns][nk].count(np)) ndp[ns][nk][np] = 0;
                        ndp[ns][nk][np] += q.second;
                    }
                }
            }
        }
        std::swap(dp, ndp);
    }

    lint ans = 0;
    for (int s = 0; s <= sum; ++s) {
        for (int k = 0; k <= 2; ++k) {
            for (const auto& q : dp[s][k]) {
                auto p = q.first;

                if (s < sum ||
                    (s == sum && p < prod) ||
                    (s == sum && p == prod && k < 1)) {
                    ans += q.second;
                }
            }
        }
    }

    std::cout << ans << std::endl;
}

int main() {
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    std::ios::sync_with_stdio(false);

    solve();

    return 0;
}