Problem: Example

Input

20


Output

4

Solution (in CPP):

Solution:
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
typedef long long int lli;

int main(){
    string s;
    cin >> s;
    int n=s.size();
    lli s_sum=0, s_prod=1;
    for(int i=0; i<n; i++){
        s[i] -= '0';
        s_sum += s[i];
        s_prod *= s[i]+1;
    }
    
    map<lli, lli> dp[14+1][9*14+1][3];
    dp[0][0][1][1] = 1;
    for(int i=0; i<n; i++){
        for(int j=0; j<=9*i; j++){
            for(int k=0; k<=9; k++){
                int next[3] = {0, (k<s[i])? 0: (k==s[i])? 1: 2, 2};
                for(int d=0; d<3; d++){
                    for(auto &p: dp[i][j][d]){
                        dp[i+1][j+k][next[d]][p.first*(k+1)] += p.second;
                    }
                }
            }
        }
    }
    
    lli ans=0;
    for(int j=0; j<=9*n; j++){
        for(int d=0; d<3; d++){
            for(auto &p: dp[n][j][d]){
                if(j<s_sum or (j==s_sum and (p.first<s_prod or (p.first==s_prod and d==0)))){
                    ans += p.second;
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}