Problem: Example

Input

20


Output

4

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
typedef pair<LL, LL> PLL;

#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

#define FF first
#define SS second
template<class S, class T>
istream& operator>>(istream& is, pair<S,T>& p){
  return is >> p.FF >> p.SS;
}

const double EPS = 1e-10;
const double PI  = acos(-1.0);
const LL MOD = 1e9+7;

LL fact[16];
int D;
LL calsum(LL x){
  LL s = 0;
  while(x > 0){
	s += x%10;
	x /= 10;
  }
  return s;
}
LL calprod(LL x){
  LL s = 1;
  while(x > 0){
	s *= (x%10)+1;
	x /= 10;
  }
  return s;
}

LL f1(int n, int d, int sum, LL tmp){
  if(d == 0)
	return tmp / fact[n];
  
  LL res = 0;
  for(int i=0;i*d<sum&&i<=n;++i){
	res += f1(n-i, d-1, sum-i*d, tmp/fact[i]);
  }

  return res;
}

LL f2(int n, int d, int sum, LL prod, LL tmp){
  LL res = 0;
  if(d == 0)
	return (sum==0? tmp / fact[n]: 0);

  for(int i=0;0<prod&&i*d<=sum&&i<=n;++i){
	res += f2(n-i, d-1, sum-d*i, prod, tmp/fact[i]);
	prod /= d+1;
  }
  return res;
}

LL powm(LL a, LL b){
  if(b==0)return 1;
  return pow(a*a,b/2)*(b%2?a:1);
}

LL nums[10];
string S;
LL ff(int idx){
  if(idx == D) return 1;
  LL res = 0;
  for(int d=0;d<10;++d){
	if(nums[d] == 0) continue;
	nums[d]--;
	if(S[idx] > '0'+d){
	  LL n = 0;
	  for(int dd=0;dd<10;++dd) n += nums[dd];
	  n = fact[n];
	  for(int dd=0;dd<10;++dd) n /= fact[nums[dd]];
	  res += n;
	}
	else if(S[idx] == '0'+d){
	  res += ff(idx+1);
	}
	nums[d]++;
  }
  
  return res;
}
LL f3(int n, int d, int sum, LL prod){
  LL res = 0;
  if(d == 0){
	nums[d] = n;
	return (sum==0 && prod==1? ff(0): 0);
  }

  for(int i=0;0<prod&&i*d<=sum&&i<=n;++i){
	nums[d] = i;
	res += f3(n-i, d-1, sum-d*i, prod);
	if(prod%(d+1) != 0) break;
	prod /= d+1;
  }
  return res;
}

int main(){
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  fact[0] =1;
  REP(i,16-1) fact[i+1] = fact[i] * (i+1);

  cin >> S;
  LL N = stoll(S);
  D = SZ(S);
  LL ans = 0, s = calsum(N), p = calprod(N);

  ans += f1(D,9,s,fact[D]);
  ans += f2(D,9,s,p-1,fact[D]);
  ans += f3(D,9,s,p);

  cout << ans-1 << endl;
  return 0;
}