Problem: Example

Input

20


Output

4

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

string str;
ll tsum=0,tmul=1;
vector<ll> t;
map<ll,ll> mem[20][200][3];

ll rec(int p,ll sum,ll mul,int flg){
  if(sum>tsum)return 0;

  if(p==(int)t.size()){
    if(sum<tsum)return 1;
    if(sum==tsum&&mul<tmul)return 1;
    if(sum==tsum&&mul==tmul&&flg==1)return 1;
    return 0;
  }

  if(mem[p][sum][flg].count(mul)>0){
    return mem[p][sum][flg][mul];
  }

  ll l=0,r=9,res=0;

  for(ll i=l;i<=r;i++){
    int nflg=flg;
    if(flg==0){
      if(i<t[p])nflg=1;
      if(i>t[p])nflg=2;
    }
    res+=rec(p+1,sum+i,mul*(i+1),nflg);
  }
  
  return mem[p][sum][flg][mul]=res;
}

int main(){
  cin>>str;
  for(int i=0;i<(int)str.size();i++){
    ll A=str[i]-'0';
    tsum+=A;
    tmul*=(A+1);
    t.push_back(A);
  }
  cout<<rec(0,0,1,0)<<endl;
  return 0;
}