Problem: Example

Input

20


Output

4

Solution (in CPP):

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

int n;
int d[14];
int sum;
ll prod;

// sum???????????§prod?????????
map<ll, ll> dp1[15][140];// [i][sum][prod]
ll f1(){
	dp1[0][0][1] = 1;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < 140; j++){
			if(dp1[i][j].size() == 0) continue;
			for(auto v : dp1[i][j]){
				ll p = v.first, cnt = v.second;
				for(int k = 0; k < 10; k++){
					ll np = p * (k + 1);
					dp1[i + 1][j + k][np] += cnt;
				}
			}
		}
	}

	ll ret = 0;
	for(int j = 0; j <= sum; j++){
		for(auto v : dp1[n][j]){
			ll p = v.first, cnt = v.second;
			if(j < sum || j == sum && p < prod) ret += cnt;
		}
	}
	return ret;
}

// sum,prod???????????§int?????????
map<ll, ll> dp2[15][2][140];// [i][eq][sum][prod]
ll f2(){
	dp2[0][1][0][1] = 1;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < 2; j++){
			for(int k = 0; k < 140; k++){
				if(dp2[i][j][k].size() == 0) continue;
				for(auto v : dp2[i][j][k]){
					ll p = v.first, cnt = v.second;
					for(int l = 0; l < 10; l++){
						if(j && d[i] < l) continue;
						int neq = j && (d[i] == l);
						ll np = p * (l + 1);
						dp2[i + 1][neq][k + l][np] += cnt;
					}
				}
			}
		}
	}

	ll ret = 0;
	for(auto v : dp2[n][0][sum]){
		ll p = v.first, cnt = v.second;
		if(p == prod) ret += cnt;
	}
	return ret;
}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
#ifdef LOCAL
	std::ifstream in("in");
	std::cin.rdbuf(in.rdbuf());
#endif

	string s;
	cin >> s;
	n = s.size();
	prod = 1;
	for(int i = 0; i < n; i++){
		d[i] = s[i] - '0';
		sum += d[i];
		prod *= d[i] + 1;
	}

	ll ans = 0;
	ans += f1();
	ans += f2();
	cout << ans << endl;
}