Problem: Example

Input

20


Output

4

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
using namespace std;

using lint = long long;

map<lint, lint> dp1[15][127];
map<lint, lint> dp2[15][2][127];

lint sum(const string& d){
    lint res = 0;
    for(auto c : d){
        res += c - '0';
    }
    return res;
}

lint prod(const string& d){
    lint res = 1;
    for(auto c : d){
        res *= c - '0' + 1LL;
    }
    return res;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    string d;
    cin >> d;

    const int n = (int)d.size();

    lint S = sum(d);
    lint P = prod(d);

    dp1[0][0][1] = 1;
    dp2[0][0][0][1] = 1;

    for(int i = 0 ; i < n ; ++i){
        for(int j = 0 ; j <= S ; ++j){
            for(int x = 0 ; x < 10 ; ++x){
                if(j + x <= S){
                    for(auto p : dp1[i][j]){
                        dp1[i + 1][j + x][p.first * (x + 1LL)] += p.second;
                    }
                }
            }
        }
        for(int j = 0 ; j < 2 ; ++j){
            int D = j ? 9 : d[i] - '0';
            for(int k = 0 ; k <= S ; ++k){
                for(int x = 0 ; x <= D ; ++x){
                    if(k + x <= S){
                        for(auto p : dp2[i][j][k]){
                            dp2[i + 1][j || x < D][k + x][p.first * (x + 1LL)] += p.second;
                        }
                    }
                }
            }
        }
    }

    lint ans = 0;

    for(int j = 0 ; j < S ; ++j){
        for(auto p : dp1[n][j]){
            ans += p.second;
        }
    }

    for(auto p : dp1[n][S]){
        if(p.first < P){
            ans += p.second;
        }
    }

    ans += dp2[n][1][S][P];

    cout << ans << endl;

    return 0;
}