Problem: Example

Input

20


Output

4

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,k,n) for(int i = (int)(k); i < (int)(n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) a.begin(), a.end()
#define MS(m,v) memset(m,v,sizeof(m))
typedef long long ll;
typedef long double ld;
typedef vector<ll> vi;
typedef vector<string> vs;
typedef pair<int, int> pii;
const int MOD = 1000000007;
const int INF = MOD + 1;
const ld EPS = 1e-12;
template<class T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<class T> T &chmax(T &a, const T &b) { return a = max(a, b); }

/*--------------------template--------------------*/

ll dp1[15][155];
ll n;
string s;
ll ssum, sprod;

ll fact(ll n)
{
	if (n == 0 || n == 1) return 1;
	return n*(fact(n - 1));
}

ll comb(ll n, ll m)
{
	return fact(n) / fact(n - m) / fact(m);
}

ll calc(vi& v, ll p)
{
	ll res = 1;
	ll m = p;
	REP(i, 10)
	{
		res *= comb(m, v[i]);
		m -= v[i];
	}
	return res;
}

ll calc2(vi& v, ll p)
{
	if (p == n) return 0;
	ll tmp = s[p] - '0';
	ll res = 0;
	REP(i, tmp)
	{
		if (v[i] > 0)
		{
			vi cp = v;
			cp[i]--;
			res += calc(cp, n - p - 1);
		}
	}
	if (v[tmp] > 0)
	{
		vi cp = v;
		cp[tmp]--;
		res += calc2(cp, p + 1);
	}
	return res;
}


ll count_sum(ll rem, ll sum)
{
	if (rem == 0)
	{
		if(sum == 0) return 1;
		else return 0;
	}
	if (dp1[rem][sum] >= 0) return dp1[rem][sum];
	ll res = 0;
	REP(i, 10)
	{
		if (sum >= i) res += count_sum(rem - 1, sum - i);
		else break;
	}
	return dp1[rem][sum] = res;
}

ll solve(vi cnt, ll tmp, ll rem, ll sum, ll prod)
{
	if (tmp == 10) return 0;
	if (rem == 0)
	{
		ll res;
		if (sum < 0 || sum == 0 && prod > sprod) return 0;
		else if (sum > 0 || sum == 0 && prod < sprod)
		{
			res = calc(cnt, n);
		}
		else if (sum == 0 && prod == sprod)
		{
			res = calc2(cnt, 0);
		}
		return res;
	}
	//if (sum < tmp * rem || prod > sprod) return 0;
	ll res = 0;
	vi cp = cnt;
	cp[tmp]++;
	res += solve(cp, tmp, rem - 1, sum - tmp, prod * (tmp + 1));
	res += solve(cnt, tmp + 1, rem, sum, prod);
	return res;
}

int main()
{
	cin.sync_with_stdio(false); cout << fixed << setprecision(10);
	MS(dp1, -1);
	cin >> s;
	n = s.size();
	ssum = 0, sprod = 1;
	for (auto i : s)
	{
		ll tmp = i - '0';
		ssum += tmp;
		sprod *= tmp + 1;
	}
	vi v(10);
	cout << solve(v, 0, n, ssum, 1) << endl;
	return 0;
}