Problem: Example

Input

20


Output

4

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
 
using ll = long long int;
using ull = unsigned long long int;
using P = pair<ll, ll>;

ll sum(ll x){
    ll res = 0;
    while(x > 0){
        res += x%10;
        x /= 10;
    }
    return res;
}

ll prod(ll x){
    ll res = 1;
    while(x > 0){
        res *= (x%10+1);
        x /= 10;
    }
    return res;
}

map<ll,ll> dp[15][3][150];

int main(){
    string d;
    cin >> d;
    int n = d.size();
    ll S = sum(stoll(d)), P = prod(stoll(d));
    dp[0][1][0][1] = 1;
    for(int i=0;i<n;i++){
        int D = d[i] - '0';
        for(int f=0;f<3;f++){
            for(int j=0;j<=S;j++){
                for(int x = 0; x <= 9; x++){
                    if(j+x <= S){
                        for(auto p : dp[i][f][j]){
                            int k = 1;
                            if(x < D) k = 0;
                            if(x > D) k = 2;
                            dp[i+1][(f!=1?f:k)][j+x][p.first*(x+1)] += dp[i][f][j][p.first];
                        }
                    }
                }
            }
        }
    }
    ll ans = 0;
    for(int i=0;i<S;i++){
        for(int f=0;f<3;f++){
            for(auto p : dp[n][f][i]){
                ans += p.second;
            }
        }
    }
    for(int f=0;f<3;f++){
        for(auto p : dp[n][f][S]){
            if(p.first < P){
                ans += p.second;
            }
        }
    }
    for(auto p : dp[n][0][S]){
        if(p.first == P) ans += p.second;
    }
    cout << ans << endl;
    return 0;
}