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));
    }
  }
  //if(p<3) cout<<p<<" "<<f<<" "<<ss<<" "<<m<<" "<<res<<endl;
  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];
  //cout<<ans<<endl;
  
  ans+=dfs(0,0,sum,pro);
  
  //cout<<ans<<endl;
  ans+=dfs2(0,sum,1);
  
  cout<<ans<<endl;
  return 0;
}