Problem: Example

Input

20


Output

4

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
map<ll,ll> mm[20][150],dp3[20][2][150];
ll n,sum=0,pro=1,ans=0;;
string s;
ll dfs(ll p,ll f,ll ss,ll m){
  if(dp3[p][f][ss].find(m)!=dp3[p][f][ss].end()) return dp3[p][f][ss][m];
  ll res=0;
  if(p==n) return f&&ss==0&&m==1;
  if(f){
    for(ll i=0;i<10;i++) if((i<=ss)&&(m%(i+1)==0)) res+=dfs(p+1,1,ss-i,m/(i+1));
  }else{
    for(ll i=0;i<s[p]-'0';i++) if((i<=ss)&&(m%(i+1)==0)) res+=dfs(p+1,1,ss-i,m/(i+1));
    ll i=s[p]-'0';
    if((i<=ss)&&(m%(i+1)==0)) res+=dfs(p+1,0,ss-i,m/(i+1));
  }
  return dp3[p][f][ss][m]=res;
}
ll dfs2(ll p,ll ss,ll m){
  if(p==n) return (ss==0&&m<pro);
  if(mm[p][ss].find(m)!=mm[p][ss].end()) return mm[p][ss][m];
  ll res=0;
  for(ll i=0;i<10;i++) if(i<=ss) res+=dfs2(p+1,ss-i,m*(i+1));
  return mm[p][ss][m]=res;
}
int main(){
  cin>>s;
  n=s.size();
  for(ll i=0;i<n;i++) sum+=s[i]-'0',pro*=(ll)(s[i]-'0'+1);
  ll dp[15][150]={};
  dp[0][0]=1;
  for(ll i=0;i<n;i++) for(ll j=0;j<150;j++) for(ll k=0;k<10;k++) dp[i+1][j+k]+=dp[i][j];
  for(ll j=0;j<sum;j++) ans+=dp[n][j];
  ans+=dfs(0,0,sum,pro)+dfs2(0,sum,1);
  cout<<ans<<endl;
  return 0;
}