Problem: Example

Input

20


Output

4

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;

string s;
int sum, mul;

map<P1,P> memo;

P dfs(int x, int S, int X){
  
  if(S>sum||(S==sum&&X>mul)) return P(0,0);
  
  if(x==s.size()){
    if(S<sum) return P(1,0);
    if(S==sum&&X<mul) return P(0,1);
    return P(0,0);
  }
  
  if(memo.count(P1(x,P(S,X)))) return memo[P1(x,P(S,X))];
  
  P res=P(0,0);
  
  for(int i=0;i<10;i++){
    P r=dfs(x+1, S+i, X*(i+1));
    res.first+=r.first;
    res.second+=r.second;
  }
  
  return memo[P1(x,P(S,X))]=res;
}

map<P,int> memo2[500][3];

int dfs2(int x, int S, int X, int flag){
  
  if(S>sum||X>mul) return 0;
  if(S+9*(s.size()-x)<sum) return 0;
  
  if(x==s.size()){
    if(S==sum&&X==mul&&flag) return 1;
    return 0;
  }
  
  if(memo2[S][flag].count(P(x,X))) return memo2[S][flag][P(x,X)];
  
  int res=0;
  
  for(int i=0;i<10;i++){
    if(flag==0&&i>s[x]-'0') continue;
    if(flag==0&&i<s[x]-'0') res+=dfs2(x+1, S+i, X*(i+1), 1);
    else res+=dfs2(x+1, S+i, X*(i+1), flag);
  }
  
  return memo2[S][flag][P(x,X)]=res;
}

signed main(){
  
  cin>>s;

  mul=1;
  for(int i=0;i<s.size();i++){
    sum+=s[i]-'0';
    mul*=(s[i]-'0'+1);
  }
  
  P ans=dfs(0,0,1);
 
  cout<<ans.first+ans.second+dfs2(0,0,1,0)<<endl;
  
  return 0;
}