Problem: Example

Input

20


Output

4

Solution (in CPP):

Solution:


#if 1
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <array>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdint>
#include <functional>
#include <iomanip>
#include <numeric>
#include <assert.h>
#include <bitset>
#include <list>

auto& in = std::cin;
auto& out = std::cout;
#define all_range(C) std::begin(C), std::end(C)
const double PI = 3.141592653589793238462643383279502884197169399375105820974944;


template<typename T, typename U>
void fill_all(T& v, const U& p) {
	v = p;
}
template<typename T, size_t N, typename U>
void fill_all(T(& v)[N], const U& p) {
	for (auto& i : v) { fill_all(i, p); }
}

int32_t N;
std::string S;
int32_t in_sum;
int64_t in_multi;
int64_t func3(int32_t i, int32_t sum, int64_t multi, int over)
{
	if (i == N) {
		if (sum > 0) {
			return 1;
		}
		if (sum == 0 && multi < in_multi) {
			return 1;
		}
		if (sum == 0 && multi == in_multi && over==1) {
			return 1;
		}
		return 0;
	}
	static std::unordered_map<int64_t, int64_t> dp[14][9 * 14 + 1][3];

	if (dp[i][sum][over].count(multi) > 0) {
		return dp[i][sum][over][multi];
	}
	auto& memo = dp[i][sum][over][multi];
	for (int32_t x = 0; x <= std::min(sum, 9); x++)
	{
		int next_over = over;
		if (next_over == 0) {
			if (x < S[i]) {
				next_over = 1;
			}
			else if(x==S[i]){
				next_over = 0;
			}
			else {
				next_over = 2;
			}
		}
		memo += func3(i + 1, sum - x, multi*(x + 1), next_over);
	}
	return memo;
}

int main()
{
	using std::endl;
	in.sync_with_stdio(false);
	out.sync_with_stdio(false);
	in.tie(nullptr);
	out.tie(nullptr);

	in >> S; N = S.size();
	for (auto& i : S) {
		i -= '0';
	}
	in_sum = 0;
	in_multi = 1;
	for (auto& i : S) {
		in_sum += i;
		in_multi *= (i+1);
	}

	out << func3(0, in_sum, 1, 0) << endl;

	return 0;
}
#endif