Problem: Example

Input

20


Output

4

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
#define int long long
using namespace std;

string s;

int sum,prod=1;
map<int,int> dp[20][3][155];

int dfs(int idx,int tight=true,int A=0,int B=1){
  if(idx==s.size()){
    if(A<sum)return 1;
    else if(A==sum&&B<prod)return 1;
    else if(A==sum&&B==prod&&tight==0)return 1;
    return 0;
  }
  if(dp[idx][tight][A].count(B))return dp[idx][tight][A][B];
  int x=s[idx]-'0';
  int r=(tight?x:9);
  for(int i=0;i<=9;i++){
    if(tight==2||tight==1&&r<i)dp[idx][tight][A][B]+=dfs(idx+1,2,A+i,B*(i+1));
    else dp[idx][tight][A][B]+=dfs(idx+1,tight&&i==r,A+i,B*(i+1));
  }
  return dp[idx][tight][A][B];
}

signed main(){
  cin>>s;
  r(i,s.size())sum+=(s[i]-'0');
  r(i,s.size())prod*=(s[i]-'0'+1);
  cout<<dfs(0)<<endl;
}