Problem: Example

Input

20


Output

4

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
char s[20];
int nn[20];
unordered_map<long long, long long> dp[20][150][3];
__inline int upd(int b, int d, int x) {
	if (b == 0) return 0;
	if (b == 2) return 2;
	if (d < x) return 0;
	if (d == x) return 1;
	return 2;
}
int main() {
	scanf("%s", s + 1);
	int n = (int) strlen(s + 1);
	for (int i = 1; i <= n; ++ i) nn[i] = s[i] - '0';
	dp[0][0][1][1] = 1;
	for (int i = 1; i <= n; ++ i) {
		for (int d = 0; d <= 9; ++ d) {
			for (int a = 0; a <= i * 9; ++ a) {
				for (int b = 0; b <= 2; ++ b) {
					for (auto x : dp[i - 1][a][b]) {
						dp[i][a + d][upd(b, d, nn[i])][x.first * (d + 1)] += x.second;
					}
				}
			}
		}
	}
	int S = 0;
	long long M = 1;
	for (int i = 1; i <= n; ++ i) {
		S += nn[i];
		M = M * (1 + nn[i]);
	}
	long long ans = 0;
	for (int i = 0; i <= S - 1; ++ i) {
		for (int b = 0; b <= 2; ++ b) {
			for (auto x : dp[n][i][b]) ans += x.second;
		}
	}
	for (int b = 0; b <= 2; ++ b)
	for (auto x : dp[n][S][b]) if (x.first < M) ans += x.second;
	for (auto x : dp[n][S][0]) if (x.first == M) ans += x.second;
	printf("%lld\n", ans);
}