Problem: Example

Input

20


Output

4

Solution (in CPP):

Solution:
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
ll f[2][10 * 14 + 2][20000][3];
ll n;
vector <ll> Hash;
int go[20010][10];
int number[15];
void init(){
    set <ll> s;
    s.insert(1);
    for (int i = 1; i <= 14; ++ i){
        set <ll> st;

        for (ll x : s){
            for (int j = 1; j <= 10; ++ j){
                st.insert(x * j);
            }
        }
        for (ll x : st){
            s.insert(x);
        }
    }

    for (ll x : s){
        Hash.push_back(x);
    }
}
int getID(ll x){
    int pos = lower_bound(Hash.begin(), Hash.end(), x) - Hash.begin();
    return pos;
}
char ch[20];
int main(){
    init();
    scanf("%s", ch);
    int len = strlen(ch);

    int ySum = 0;

    for (int i = len - 1; i >= 0; -- i){
        number[len - i] = ch[i] - '0';
        ySum += ch[i] - '0';
    }
    n = 1;
    for (int i = 0; i < len; ++ i){
        n = n * (ch[i] - '0' + 1);
    }

    int num = Hash.size();
    int yID = getID(n);

    for (int i = 0; i < num; ++ i){
        for (int j = 1; j <= 10; ++ j){
            int id = getID(Hash[i] * j);
            go[i][j - 1] = id;
        }
    }
    //printf("%d %lld\n", ySum, n);
    for (int j = 0; j <= 9 * 14; ++ j){
        for (int k = 0; k < num; ++ k){
            for (int l = 0; l <= 2; ++ l){
                if (j < ySum){
                    f[0][j][k][l] = 1;
                }
                if (j == ySum && k < yID){
                    f[0][j][k][l] = 1;
                }
                if (j == ySum && k == yID && l == 0){
                    f[0][j][k][l] = 1;
                }
            }
        }
    }
    //for (int i = 1; i <= len; ++ i) printf("%d ", number[i]); puts("");
    ll pow10[15];
    pow10[0] = 1;
    for (int i = 1; i <= 14; ++ i) pow10[i] = pow10[i - 1] * 10;
    //puts("da");
    int now = 0, nxt = 1;
    for (int i = 1; i <= len; ++ i){
        //printf("%d\n", i);
        memset(f[nxt], 0, sizeof f[nxt]);
        for (int j = 0; j <= 9 * (len - i); ++ j){
            for (int k = 0; k < num; ++ k){

                for (int l = 0; l <= 2; ++ l){
                    int maxn = number[i];
                    for (int m = 0; m <= 9; ++ m){
                        int status = go[k][m];
                        //if (m < 2 && i == 2 && j == 0 && k == 0 && l == 1) printf("%d %d %d\n", j + m, maxn, l & (m == maxn));
                        if (l == 1){
                            int flag = 1;
                            if (m > maxn) flag = 2;
                            else if (m < maxn) flag = 0;
                            f[nxt][j][k][l] += f[now][j + m][status][flag];
                        } else
                            f[nxt][j][k][l] += f[now][j + m][status][l];
                    }
                }
            }
        }
        swap(now, nxt);
    }
    //printf("%lld\n", f[2][0][0][1]);
    //printf("%lld\n", f[0][2][2][0]);
    //printf("%lld\n", f[0][1][1][0]);
    //printf("%lld\n", f[0][0][0][0]);
    printf("%lld\n", f[now][0][0][1]);
}