Problem: Example

Input

20


Output

4

Solution (in CPP):

Solution:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <cassert>
#include <queue>

using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define ft first
#define sd second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long LL;
typedef pair<int,int> PII;
typedef queue<int> QI;

const LL mod=1000000007;
LL powmod(LL a,LL b) {LL res=1;a%=mod;for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
// head

LL jc[15],l;

//LL g[14][14*9+1]
char s[23];
map<LL,LL>f[14][14*9+1][3];

map<LL,LL>::iterator it;

void init(){
    //jc[0]=1;rep(i,0,15)jc[i]=jc[i-1]*i;
    rep(i,0,s[0]-'0')f[0][i][0][i+1]=1;
    f[0][s[0]-'0'][1][s[0]-'0'+1]=1;

    rep(i,0,10)f[0][i][2][i+1]=1;

   // cout<<f[0][0][1][1]<<endl;
    rep(i,0,l-1){
        rep(j,0,9*(i+2)){
            rep(now,0,3){//cout<<i<<' '<<j<<' '<<now<<endl;
            for(it=f[i][j][now].begin();it!=f[i][j][now].end();++it){
                //cout<<i<<' '<<j<<' '<<now<<endl;
                LL p=(*it).ft,v=(*it).sd;
                int nxt=0,nn=s[i+1]-'0';
                if(now!=2)rep(k,0,10){
                    if(now==1 && k==nn)nxt=1;
                    if(now==1 && k>nn)break;
                    f[i+1][j+k][nxt][p*(k+1)]+=v;
                }else{
                    rep(k,0,10){
                        f[i+1][j+k][2][p*(k+1)]+=v;
                    }
                }
            }
        }
    }
}
}


int main(){
    while(~scanf("%s",s)){
        LL ans=0,sum=0,pro=1,num=0;
        l=strlen(s);init();rep(i,0,l){
            sum+=s[i]-'0';
            pro*=(s[i]-'0')+1;
            num*=10;
            num+=s[i]-'0';
        }
     //   cout<<sum<<' '<<pro<<' '<<num<<endl;
       rep(i,0,sum){
            for(it=f[l-1][i][2].begin();it!=f[l-1][i][2].end();++it){
                ans+=(*it).sd;
            }
        }
        for(it=f[l-1][sum][2].begin();it!=f[l-1][sum][2].end();++it){
            if((*it).ft<pro)ans+=(*it).sd;
        }
        ans+=f[l-1][sum][0][pro];
        cout<<ans<<endl;
    }
	return 0;
}