Problem: Example

Input

20


Output

4

Solution (in CPP):

Solution:
#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>
#include <string>
using namespace std;

vector<tuple<long long, long long, string>>vec;
string V; int N; long long fact[15];

void dfs(int pos, long long sum, long long prod, string S) {
	if (pos == N) {
		vec.push_back(make_tuple(sum, prod, S));
		return;
	}
	int v = 0; if (S.size() >= 1) v = (S[S.size() - 1] - '0');

	for (int i = v; i < 10; i++) {
		string SS = S; SS += ('0' + i);
		dfs(pos + 1, sum + i, prod * (i + 1), SS);
	}
}

long long anagram(string A1, string A2) {
	int t[10]; for (int i = 0; i < 10; i++) t[i] = 0;
	for (int i = 0; i < A1.size(); i++) t[A1[i] - '0']++;

	long long rem = 0;
	for (int i = 0; i < A2.size(); i++) {
		for (int j = 0; j < (A2[i] - '0'); j++) {
			if (t[j] == 0) continue;
			t[j]--;
			long long D = fact[N - 1 - i];
			for (int k = 0; k < 10; k++) D /= fact[t[k]];
			t[j]++;
			rem += D;
		}
		t[A2[i] - '0']--;
		if (t[A2[i] - '0'] == -1) return rem;
	}
	return rem + 1;
}

long long anagram2(string A1) {
	int t[10]; for (int i = 0; i < 10; i++) t[i] = 0;
	for (int i = 0; i < A1.size(); i++) t[A1[i] - '0']++;

	long long r = fact[N];
	for (int i = 0; i < 10; i++) r /= fact[t[i]];
	return r;
}

int main() {
	fact[0] = 1; for (int i = 1; i <= 14; i++) fact[i] = 1LL * fact[i - 1] * i;
	cin >> V; N = V.size();
	dfs(0, 0, 1, "");
	sort(vec.begin(), vec.end());

	tuple<long long, long long, string>W;
	long long s1 = 0, s2 = 1; for (int i = 0; i < V.size(); i++) { s1 += (V[i] - '0'); s2 *= (long long)(V[i] - '0' + 1); }
	W = make_tuple(s1, s2, V); sort(get<2>(W).begin(), get<2>(W).end());

	long long ans = 0;
	for (int i = 0; i < vec.size(); i++) {
		if (make_pair(get<0>(vec[i]), get<1>(vec[i])) < make_pair(get<0>(W), get<1>(W))) {
			string D = get<2>(vec[i]); sort(D.begin(), D.end()); reverse(D.begin(), D.end());
			ans += anagram2(get<2>(vec[i]));
		}
		else if (make_pair(get<0>(vec[i]), get<1>(vec[i])) == make_pair(get<0>(W), get<1>(W))) {
			ans += anagram(get<2>(vec[i]), V);
		}
	}
	cout << ans - 1 << endl;
	return 0;
}