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<vector<int>> com;
LL dp[20][2];

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

vector<LL> inv;

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 dp[k][t]=res;
}


int main(){
    string s;cin >> s;
    int n=s.length();
    memset(dp,-1,sizeof(dp));
    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;
    }
    combination(n+9,9,0,vector<int> (0));
    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=0;j<com[i].size()-1;j++){
            LL x=com[i][j+1]-com[i][j]-1;
            sum+=x*(j+1);
            k/=inv[x];
            ss[j+1]=x;
            while(x--) t*=j+2;
        }
        if(sum<sum0) ans+=k;
        else if(sum==sum0&&t<t0) ans+=k;
        else if(sum==sum0&&t==t0){
            ans+=rec(0,true,s,ss);
        }
    }
    cout << ans << endl;
    return 0;
}