Problem: Example

Input

20


Output

4

Solution (in CPP):

Solution:
#include<iostream>
#include<list>
#include<string>
#include<cstring>
#include<sstream>
#include<cctype>
#include<string.h>
#include<algorithm>
#include<cmath>
#include<stack>
#include<fstream>
#include<cstdlib>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
#include<queue>
using namespace std;

#define LL long long int
#define uLL unsigned long long int

#define S(a) scanf("%d",&a)
#define S2(a,b) scanf("%d%d",&a,&b)
#define S3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define SLL(a) scanf("%lld",&a)
#define SLL2(a,b) scanf("%lld%lld",&a,&b)
#define SLL3(a,b,c) scanf("%lld%lld%lld",&a,&b,&c)
#define SC(a) scanf("%c",&a)
#define P(a) printf("%d",a)
#define PS(a) printf("%s",a)
#define PLL(a) printf("%lld",a)
#define PCASE(kk) printf("Case %d: ",kk++)
#define PCASENL(kk) printf("Case %d:\n",kk++)
#define NL puts("")

#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define pi (2.0*acos(0.0))
#define pii pair<int,int>

template<typename T>inline T POW(T B,T P)
{
    if(P==0) return 1;
    if(P&1) return B*POW(B,P-1);
    else return SQR(POW(B,P/2));
}
template <class T> inline T BMOD(T p,T e,T m)
{
    T ret=1;
    while(e)
    {
        if(e&1) ret=(ret*p)%m;
        p=(p*p)%m;
        e>>=1;
    }
    return (T)ret;
}
template <typename T>inline T ModInv (T b,T m)
{
    return BMOD(b,m-2,m);
}
template<typename T>inline T ABS(T a)
{
    if(a<0)return -a;
    else return a;
}
template<typename T>inline T gcd(T a,T b)
{
    if(a<0)return gcd(-a,b);
    if(b<0)return gcd(a,-b);
    return (b==0)?a:gcd(b,a%b);
}
template<typename T>inline T lcm(T a,T b)
{
    if(a<0)return lcm(-a,b);
    if(b<0)return lcm(a,-b);
    return a*(b/gcd(a,b));
}

/////////////////////////////////////////////////


LL n,ss,pp,dp[15][3][130][20004],val[20004];
int dg[15],l,uid,tc,vis[15][3][130][20004];
//vector<int>dg;
char ch[15];
map< pair< pair<int,int> , pair<int,LL> >,LL >MP;
map<LL,int> hs;
LL go(int pos,int fl,int sum,int  id)
{
//    cout<<pos<<" "<<sum<<" "<<val[id]<<endl;
    if(sum>ss)return 0;
    else if(sum==ss && val[id]>pp)return 0;
    else if(sum==ss && val[id]==pp && fl==2)return 0;

//    if(fl==2 && sum==ss && prod==pp)return 0;

    if(pos==l && sum<ss)return 1;
    else if(pos==l && sum==ss && val[id]<pp)return 1;
    else if(pos==l && sum==ss && val[id]==pp && fl==1)return 1;
    else if(pos==l && sum==ss && val[id]==pp && fl!=1)return 0;
//    else if(pos==l)return 0;

//    if(MP.find(mp(mp(pos,fl),mp(sum,prod)))!=MP.end())return MP[mp(mp(pos,fl),mp(sum,prod) )];
    if(vis[pos][fl][sum][id]==tc)return dp[pos][fl][sum][id];
    vis[pos][fl][sum][id]=tc;
    LL ret=0;
    int lm=dg[pos];
    if(fl==1)lm=9;
    if(fl==2)lm=9;
//    cout<<lm<<endl;
    for(int i=0; i<=9; i++)
    {
        LL gt =val[id]*(i+1);
        int nw_id;
        if(hs.find(gt)!=hs.end()) nw_id = hs[gt];
        else
        {
            uid++;
            hs[gt] = uid;
            val[uid]=gt;
            nw_id = uid;
        }
        if(fl==0 && i<lm)ret+=go(pos+1,1,sum+i,nw_id);
        else if(fl==0 && i==lm)ret+=go(pos+1,fl,sum+i,nw_id);
        else if(fl==0 && i>lm)ret+=go(pos+1,2,sum+i,nw_id);
        else if(fl==1 )ret+=go(pos+1,fl,sum+i,nw_id);
        else if(fl==2 )ret+=go(pos+1,fl,sum+i,nw_id);
    }
//    MP[mp(mp(pos,fl),mp(sum,prod) )]=ret;
    dp[pos][fl][sum][id]=ret;
    return ret;
}

int main()
{
    uid = 1;
    hs[1] = uid;
    val[uid]=1;
    tc=1;
//    cout<<"asdf"<<endl;
    scanf("%s",ch);
//        for(int i=0;i<14;i++)ch[i]='9';
    //MP.clear();
    l=strlen(ch);
    ss=0;
    pp=1;
    for(int i=0; i<l; i++)
    {
        dg[i]=ch[i]-'0';
        ss+=dg[i];
        pp*=(dg[i]+1);
//            cout<<dg[i]<<" ";
    }
//        puts("");
    //memset(dp,-1,sizeof dp);

    LL res=go(0,0,0,1);
    printf("%lld\n",res);
//        cout<<uid<<endl;
    //hs.clear();
//        memset()
    tc++;

    return 0;
}