Problem: Example

Input

20


Output

4

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll Asum,Aprod,Aint;
int n;
string A,B;

ll nCr(int n, int r){
  static ll mem[20][20]={};
  if(mem[n][r]!=0)return mem[n][r];
  if(r==0||n==r)return 1;
  ll a=1;
  for(int i=0;i<r;i++) a*=(n-i);
  for(int i=0;i<r;i++) a/=(i+1);
  return mem[n][r]=a;
}

ll Sum(string str){
  ll res=0;
  for(int i=0;i<str.size();i++)res+=str[i]-'0';
  return res;
}

ll Prod(string str){
  ll res=1;
  for(int i=0;i<str.size();i++)res*=str[i]-'0'+1;
  return res;
}

ll Int(string str){
  ll res=0;
  for(int i=0;i<str.size();i++)res=res*10+str[i]-'0';
  return res;
}

ll permutation(string str){
  ll n=str.size(),res=1;
  for(int i=0,cnt=1;i<n;i++){
    if(str[i]==str[i+1])cnt++;
    else res*=nCr(n-i+cnt-1,cnt),cnt=1;
  }
  return res;
}

ll permutation(vector<int> a){
  string str;
  for(int i=0;i<a.size();i++)while(a[i]--)str+=(char)(i+'0');
  return  permutation(str);
}

ll count(){
  ll res=0,m;
  vector<int>t(10),cnt(10);
  for(int i=0;i<n;i++)t[B[i]-'0']++;
  cnt=t;
  for(m=0;m<n&&t[A[m]-'0'];t[A[m++]-'0']--);
  
  for(int i=0;i<=m;i++){
    for(int j=0;j<A[i]-'0';j++)
      if(cnt[j])cnt[j]--,res+=permutation(cnt),cnt[j]++;
    cnt[A[i]-'0']--;
  }
  return res;
}



ll calc(){
  if(Asum!=Sum(B)) return (Sum(B)<Asum)*permutation(B);
  if(Aprod!=Prod(B))return (Prod(B)<Aprod)*permutation(B);
  return count();
}

ll dfs(int idx,int num,int sum){
  if(idx==n) return calc();
  if(num==10||idx==n) return 0;
  ll res=dfs(idx,num+1,sum);
  B[idx]=num+'0';
  return res+dfs(idx+1,num,sum+num);
}

int main(){
  cin>>A;
  n=A.size();
  Asum=Sum(A),Aprod=Prod(A),Aint=Int(A);
  B.resize(n);
  cout<<dfs(0,0,0)<<endl;
  return 0;
}