Problem: Example

Input

20


Output

4

Solution (in CPP):

Solution:
#include <algorithm>
#include <map>
#include <iostream>
#include <cstdio>
using namespace std;
using ll = long long int;

const int DIGIT = 14 + 1;
const int MAXS = DIGIT * 9 + 1;
map<ll, ll> dp[DIGIT][MAXS][3];

string str;
ll N, sum, prod;

ll solve(int d, int s, int f, ll p) {
    if(d == N) {
        if(s < sum) return 1;
        else if(s == sum and p < prod) return 1;
        else if(s == sum and p == prod) {
            if(f == 1) return 1;
            else return 0;
        }
        else return 0;
    }

    if(dp[d][s][f].count(p)) return dp[d][s][f][p];
    int num = str[d] - '0';
    ll res = 0;
    for(int x=0; x<=9; x++) {
        int ns = s + x;
        int nf = f;
        if(nf == 0 and x < num) nf = 1;
        if(nf == 0 and x > num) nf = 2;
        ll np = p * (x + 1);

        res += solve(d+1, ns, nf, np);
    }
    return dp[d][s][f][p] = res;
}

int main() {
    cin >> str;
    N = str.length(); prod = 1;
    for(int i=0; i<N; i++) {
        int c = str[i] - '0';
        sum += c;
        prod *= (c + 1);
    }

    cout << solve(0, 0, 0, 1) << endl;
    return 0;
}