Problem: Example

Input

20


Output

4

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long LL;
typedef pair<LL,int> P;
const LL mod=1000000007;
const LL LINF=1LL<<62;
const LL INF=1<<17;

vector<LL> inv;

vector<vector<int>> combination(int n,int r,int k,vector<int> v){
    if(r==k){
        return vector<vector<int>> (1,v);
    }
    vector<vector<int>> ret;
    for(int i=(k==0?0:v[k-1]+1);i<=n-r+k;i++){
        v.push_back(i);
        auto p=combination(n,r,k+1,v);
        copy(ALL(p),back_inserter(ret));
        v.erase(v.end()-1);
    }
    return ret;
}


LL rec(int k,bool t,string s,vector<int> ss){
    if(k==s.length()&&!t) return 1;
    int x=s[k]-'0';
    int mx=t?x:9;
    LL res=0LL;
    if(t){
        for(int i=0;i<=mx;i++){
            if(ss[i]==0) continue;
            ss[i]--;
            res+=rec(k+1,t&&i==mx,s,ss);
            ss[i]++;
        }
    }
    else{
        res=inv[s.length()-k];
        for(int i=0;i<10;i++) res/=inv[ss[i]];
    }
    return res;
}


int main(){
    string s;cin >> s;
    int n=s.length();
    LL t0=1,sum0=0;
    for(int i=0;i<n;i++){
        t0*=s[i]-'0'+1;
        sum0+=s[i]-'0';
    }
    LL c=1;
    for(int i=1;i<16;i++){
        inv.pb(c);
        c*=i;
    }
    auto com=combination(n+9,9,0,vector<int> ());
    LL ans=0;
    for(int i=0;i<com.size();i++){
        com[i].pb(n+9);
        LL t=1,sum=0,k=inv[n]/inv[com[i][0]];
        vector<int> ss(10,0);
        ss[0]=com[i][0];
        for(int j=1;j<com[i].size();j++){
            LL x=com[i][j]-com[i][j-1]-1;
            sum+=x*j;
            k/=inv[x];
            ss[j]=x;
            while(x--) t*=j+1;
        }
        if(sum<sum0) ans+=k;
        else if(sum==sum0){
            if(t<t0) ans+=k;
            if(t==t0) ans+=rec(0,true,s,ss);
        }
    }
    cout << ans << endl;
    return 0;
}