Problem: Example

Input

20


Output

4

Solution (in CPP):

Solution:
#include <cmath>
#include <vector>
#include <iomanip>
#include <iostream>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <limits> 

using namespace std;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef long long ll;
typedef pair<int, int> PII;
typedef vector<PII> VP;

ll fact[15];
int n;
string s;
vector<string> sequences;

void generate(int m, int dig, string& seq) {
	if (m == 0) {
		sequences.push_back(seq);
		return;
	}
	if (dig == 10) return;
	for (int i = m; i >= 0; --i) {
		if (i > 0) seq += string(i, '0'+dig);
		generate(m-i, dig+1, seq);
		for (int j= 0; j < i; ++j) seq.pop_back();
	}
} 

int cmpr(const string& a, const string& b) {
	int suma = 0, sumb = 0;
	ll mula = 1, mulb = 1;
	for (auto& x : a) {
		int dig = x-'0';
		suma += dig;
		mula *= (dig+1);
	}
	for (auto& x : b) {
		int dig = x-'0';
		sumb += dig;
		mulb *= (dig+1);
	}
	if (suma == sumb && mula == mulb) return 0;
	if (suma > sumb || (suma == sumb && mula > mulb)) return 1;
	return -1;
}
ll Count(const string& a) {
	VI cnt(10, 0);
	for (auto& x : a) cnt[x-'0']++;
	ll res = fact[a.size()];
	for (auto& x : cnt) res /= fact[x];
	return res;
}
ll countme(const VI& cnt, int len) {
	ll res = fact[len];
	for (auto& x : cnt) res /= fact[x];
	return res;
}
ll CountLessThenS(string& a) {
	VI cnt(10, 0);
	for (auto& x : a) cnt[x-'0']++;
	/*VI sums(10, 0);
	sums[0] = cnt[0];
	for (int i = 1; i < 10; ++i) sums[i] = cnt[i] + sums[i-1];*/
	ll sol = 0;
	int len = a.size();
	for (int i = 0; i < s.size(); ++i) {
		for (int j = 0; j < s[i]-'0'; ++j) {
			if (cnt[j]) {
				--cnt[j];
				sol += countme(cnt, len-1);
				++cnt[j];
			}
		}
		if (cnt[s[i]-'0'] == 0) return sol;
		--cnt[s[i]-'0'];
		--len;
	}
	return sol;
}

int main() {
	ios::sync_with_stdio(false);
	fact[0] = fact[1] = 1;
	for (int i = 2; i < 15; ++i) fact[i] = fact[i-1] * i;
	while (cin >> s) {
		n = s.size();
		sequences.clear();
		string tmps = "";
		generate(n, 0, tmps);
		ll sol = 0;
		for (auto& seq : sequences) {
			int cmp = cmpr(seq, s);
			if (cmp == -1)
				sol += Count(seq);
			else if (cmp == 0) {
				sol += CountLessThenS(seq);
			}
		}
		cout << sol << '\n';
	}
}