Problem: Example

Input

20


Output

4

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using int64 = long long;
string _D;

//[i][two][three][five][seven][less][sum]
//[i][less][greater][sum][flag]
map<int64, int64> dp[15][2][2][140];

map<int, int> factorize(int x) {
	map<int, int> res;
	for (int y = 2; y * y <= x; y++) {
		while (x % y == 0) {
			x /= y;
			res[y]++;
		}
	}
	if (x > 1)
		res[x]++;
	return res;
}

int main() {
	cin >> _D;
	vector<int> D;
	for (char d : _D)
		D.push_back(d - '0');
	int64 dsum = 0;
	int64 dprod = 1;

	for (int d : D) {
		dsum += d;
		dprod *= d + 1;
	}

	dp[0][0][0][0][1] = 1;
	for (int i = 0; i < D.size(); i++) {
		for (int less = 0; less <= 1; less++) {
			for (int gr = 0; gr <= 1; gr++) {
				for (int sum = 0; sum <= i * 9; sum++) {
					for (auto p : dp[i][less][gr][sum]) {
						for (int d = 0; d < 10; d++) {
							int nsum = sum + d;
							int64 nprod = p.first * (d + 1);
							int nless = less | (!gr & (d < D[i]));
							int ngr = gr | (!less & (d > D[i]));

							if (nsum > dsum)
								continue;
							if (nsum == dsum and nprod > dprod)
								continue;
							if (nsum == dsum and nprod == dprod and ngr)
								continue;

							dp[i + 1][nless][ngr][nsum][nprod] += p.second;
						}
					}
				}
			}
		}
	}

	int64 ans = 0;
	for (int less = 0; less <= 1; less++) {
		for (int gr = 0; gr <= 1; gr++) {
			for (int sum = 0; sum <= dsum; sum++) {
				for (auto p : dp[D.size()][less][gr][sum]) {
					if (sum < dsum) {
						ans += p.second;
					} else if (p.first < dprod) {
						ans += p.second;
					} else if (less) {
						ans += p.second;
					}

					/*
					 if (nsum > dsum)
					 continue;
					 if (nsum == dsum and nprod > dprod)
					 continue;
					 if (nsum == dsum and nprod == dprod and ngr)
					 continue;
					 */
				}
			}
		}
	}
	cout << ans << endl;

	return 0;

}