Problem: Example

Input

20


Output

4

Solution (in CPP):

Solution:
#include <bits/stdc++.h>

using namespace std;

typedef long long Int;

int N, S;
char s[16], s2[16];

Int memo1[16][14 * 9];

Int func1(int N, int S)
{
	if (S < 0) return (0);
	if (N == 0) return (1);
	if (~memo1[N][S]) return (memo1[N][S]);
	
	Int ans = 0;
	for (int i = 0; i <= 9; i++){
		ans += func1(N - 1, S - i);
	}
	
	return (memo1[N][S] = ans);
}

Int pos;
Int fact[15], ten[15];

Int calcComb(int *a)
{
	Int den = 1, sum = 0;
	
	for (int i = 0; i <= 9; i++){
		sum += a[i]; den *= fact[a[i]];
	}
	
	return (fact[sum] / den);
}

Int X;

void func2(int n, int sum, int l, Int tmp = 0)
{
	if (sum < 0) return;
	if (n * l < sum) return;
	
	if (n == 0){
		Int p1 = 1, p2 = 1, tmp_ = tmp, X_ = X;
		for (int i = 0; i < N; i++){
			p1 *= (tmp_ % 10 + 1); p2 *= (X_ % 10 + 1);
			tmp_ /= 10; X_ /= 10;
		}
		if (sum == 0 && p1 < p2){
			int a[10] = {0};
			for (int i = 0; i < N; i++){
				a[tmp % 10]++; tmp /= 10;
			}
			pos += calcComb(a);
		}
		if (sum == 0 && p1 == p2){
			int a[10] = {0};
			for (int i = 0; i < N; i++){
				a[tmp % 10]++; tmp /= 10;
			}
			for (int i = 0; i < N; i++){
				for (int j = 0; j < s[i] - '0'; j++){
					if (a[j]){
						a[j]--;
						pos += calcComb(a);
						a[j]++;
					}
				}
				if (a[s[i] - '0']){
					a[s[i] - '0']--;
				}
				else break;
			}
		}
		return;
	}
	
	Int orig = tmp;
	for (int i = min(l, sum); i >= 0; i--){
		tmp = tmp + i * ten[N - n];
		func2(n - 1, sum - i, i, tmp);
		tmp = orig;
	}
}

int main()
{	
	fact[0] = ten[0] = 1;
	for (int i = 1; i <= 14; i++){
		fact[i] = i * fact[i - 1];
		ten[i] = 10 * ten[i - 1];
	}
	
	scanf("%s", s);
	
	int bucket[10] = {0};
	for (int i = 0; s[i]; i++){
		S += s[i] - '0';
		N++;
		bucket[s[i] - '0']++;
	}
	
	memset(memo1, -1, sizeof(memo1));
	pos = func1(N, S - 1);
	
	strcpy(s2, s);
	sort(s2, s2 + N);
	
	for (int i = 0; s2[i]; i++){
		X = X * 10 + s2[i] - '0';
	}
	
	func2(N, S, 9);
	
	printf("%lld\n", pos);
	
	return (0);
}