Problem: Example

Input

20


Output

4

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<(n);i++)
#define all(v) (v).begin(),(v).end()
#define pb(a) push_back(a)
using namespace std;
typedef long long LL;

LL fact[20];
string d;
LL d_sum=0, d_prod=1;
int n;
vector<int> cnt(10, 0);
LL ans;
void rec(int k, vector<int> now){
    rep(i, 10){
        if(now[i] == 0) continue;
        if(i > d[k]-'0'){
            return;
        }else{
            if(i > d[k]-'0') return;
            now[i]--;
            if(i == d[k]-'0') rec(k+1, now);
            else{
                LL tmp = fact[n-k-1];
                rep(j, 10) tmp /= fact[now[j]];
                ans += tmp;
            }
            now[i]++;
        }
    }
}
    

void solve(vector<int> now){
    LL n_sum = 0, n_prod = 1;
    rep(i, 10) n_sum+=i*now[i];
    rep(i, 10)rep(j, now[i]) n_prod*=i+1;
    if(n_sum < d_sum || n_sum==d_sum&&n_prod<d_prod){
        LL tmp=fact[n];
        rep(i, 10) tmp /= fact[cnt[i]];
        ans += tmp;
    }else if(n_sum == d_sum && n_prod == d_prod){
        vector<int> rem = now;
        rec(0, rem);
    }
}    

        
void dfs(int k, int st){
    for(int i=st; i<10; i++){
        cnt[i]++;
        if(k == n-1) solve(cnt);
        else dfs(k+1, i);
        cnt[i]--;
    }
}

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

    cin >> d;
    for(auto &x: d) d_sum += x-'0';
    d_prod = 1;
    for(auto &x: d) d_prod *= (x-'0')+1;
    n = d.size();
    fact[0] = 1;
    rep1(i,16) fact[i] = i*fact[i-1];

    dfs(0, 0);
    cout << ans << endl; 
    
}