Problem: Example

Input

20


Output

4

Solution (in CPP):

Solution:
#include <string>
#include <vector>
#include <iostream>
using namespace std;
string s; int n, sums; long long prods = 1, fact[19];
long long anagram(string t) {
	int c[10] = { 0 };
	for (int i = 0; i < t.size(); i++) c[t[i] - 48]++;
	long long ret = fact[t.size()];
	for (int i = 0; i < 10; i++) ret /= fact[c[i]];
	return ret;
}
long long anagram2(int ptr, string t) {
	if (ptr == n) return 0;
	long long ret = 0;
	bool vis[26] = { false };
	for (int i = 0; i < t.size(); i++) {
		if (vis[t[i] - 48]) continue;
		if (t[i] < s[ptr]) {
			string u = t; u.erase(u.begin() + i);
			ret += anagram(u);
		}
		if (t[i] == s[ptr]) {
			string u = t; u.erase(u.begin() + i);
			ret += anagram2(ptr + 1, u);
		}
		vis[t[i] - 48] = true;
	}
	return ret;
}
long long rec(int ptr, int digit, int sum, long long prod, string x) {
	if (ptr == 10) {
		if (digit != n) return 0;
		if (sum != sums) return (sum < sums ? anagram(x) : 0);
		if (prod != prods) return (prod < prods ? anagram(x) : 0);
		return anagram2(0, x);
	}
	long long ret = 0;
	for (int i = 0; digit + i <= n; i++) {
		ret += rec(ptr + 1, digit + i, sum, prod, x);
		sum += ptr;
		prod *= (ptr + 1);
		x += ptr + 48;
	}
	return ret;
}
int main() {
	cin >> s; n = s.size();
	fact[0] = 1;
	for (int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i;
	for (int i = 0; i < n; i++) {
		sums += s[i] - 48;
		prods *= s[i] - 47;
	}
	long long ret = rec(0, 0, 0, 1, "");
	cout << ret << endl;
	return 0;
}