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 prod;

void func2(int n, int sum, int l, Int tmp = 0, Int tprod = 1)
{
	if (sum < 0) return;
	if (n * l < sum) return;
	
	if (n == 0){
		if (sum == 0 && tprod < prod){
			int a[10] = {0};
			for (int i = 0; i < N; i++){
				a[tmp % 10]++; tmp /= 10;
			}
			pos += calcComb(a);
		}
		if (sum == 0 && tprod == prod){
			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, tprod * (i + 1));
		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);
	prod = 1;
	for (int i = 0; s[i]; i++){
		S += s[i] - '0';
		prod *= (s[i] - '0' + 1);
		N++;
	}
	
	memset(memo1, -1, sizeof(memo1));
	pos = func1(N, S - 1);
	
	func2(N, S, 9);
	
	printf("%lld\n", pos);
	
	return (0);
}