Problem: Example

Input

20


Output

4

Solution (in CPP):

Solution:
#include "bits/stdc++.h"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
template<class T>
using Table = vector<vector<T>>;
const ld eps=1e-9;

//// < "D:\D_Download\Visual Studio 2015\Projects\programing_contest_c++\Debug\a.txt"

long long int  fact(const int a) {
	assert(a >= 0);
	if (a == 0)return 1;
	return a*fact(a - 1);
}
long long int  comb(const int a, const int b) {
	if (!b)return 1;
	return (fact(a) / fact(b)) / fact(a - b);
}

map<pair<int, pair<long long int,long long int>>, long long int>amp;
long long int gettotal(int keta, long long int restsum, long long int restprod) {
	if (!keta) {
		if (restsum == 0 && restprod == 1)return 1;
		else return 0;
	}
	else {
		if (keta * 9 < restsum)return 0;
		if (keta <= 11) {
			if (amp.find(make_pair(keta, make_pair(restsum, restprod))) == amp.end()) {
				long long int ans = 0;
				for (int i = 0; i < 10; ++i) {
					if (restsum >= i && (restprod % (i + 1) == 0)) {
						ans += gettotal(keta - 1, restsum - i, restprod / (i + 1));
					}
				}
				return amp[make_pair(keta,make_pair(restsum,restprod))]=ans;
			}
			else {
				return amp[make_pair(keta, make_pair(restsum, restprod))];
			}
		}
		else {
			long long int ans = 0;
			for (int i = 0; i < 10; ++i) {
				if (restsum >= i && (restprod % (i + 1) == 0)) {
					ans += gettotal(keta - 1, restsum - i, restprod / (i + 1));
				}
			}
			return amp[make_pair(keta, make_pair(restsum, restprod))] = ans;
		}
		
	}
}
long long int getnum(string st,long long int restsum,long long int restprod) {
	if (st.empty()&&restsum==0&&restprod==1)return 0;
	
	const int atop(st[0] - '0');
	long long int ans = 0;
	for (int i = 0; i <= atop; ++i) {
		if (restsum >= i&&restprod % (i + 1) == 0) {
			if (i < atop) {
				ans += gettotal(st.size() - 1, restsum - i, restprod / (i + 1));
			}
			else if (i == atop) {
				ans += getnum(st.substr(1, st.size() - 1), restsum - i, restprod / (i + 1));
			}
			else {
				break;
			}
		}
		
	}
	return ans;
}

int main() {
	/*int N; cin >> N;
	vector<int>nums(N);
	for (int i = 0; i < N; ++i) {
		cin >> nums[i];
	}
	set<int>aset;
	set<int>ans;
	for (int i = 0;i< N; ++i) {
		set<int>newset;
		for (auto s : aset) {
			if (s < 1000) {
				newset.emplace(s * 10 + nums[i]);
				ans.emplace(s * 10 + nums[i]);
			}
		}
		newset.emplace(nums[i]);
		ans.emplace(nums[i]);
		aset = newset;
	}
	int n = 0;
	int finans = ans.size();
	for (auto s : ans) {
		if (s != n) {
			finans = n;
			break;
		}
		else {
			n++;
		}
	}
	cout << finans << endl;*/
	string st; cin >> st;
	int sum = 0;
	long long int prod = 1;
	for (auto c : st) {
		sum += c - '0';
		prod *= c - '0' + 1;
	}
	
	map<pair<int,long long int>, long long int >mp;
	mp[make_pair(0,1)] = 1;
	long long int ans = 0;
	for (int i = 0; i < st.size(); ++i) {
		map<pair<int,long long int>, long long int>newmp;
		for (auto m : mp) {
			for (int j = 1; j <= 10; ++j) {
				if (i == st.size() - 1) {
					if (m.first.first + j - 1 < sum) {
						ans += m.second;
						continue;
					}
					else if (m.first.first + j - 1 > sum) {
						continue;
					}
				}
				newmp[make_pair(m.first.first+j-1, m.first.second*j)] += m.second;
			}
		}
		mp = newmp;
	}
	for (auto m : mp) {
		if (m.first.second < prod)ans += m.second;
		else if (m.first.second == prod)break;
		else assert(false);
	}
	ans += getnum(st,sum,prod);
	cout << ans << endl;
	return 0;
}