Problem: Example

Input

20


Output

4

Solution (in CPP):

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

typedef long long ll;

vector<int> D;
//   digit sum flg 
map<ll, ll> dp[15][150][3];

int main(){
	string str;
	cin >> str;
	ll isum = 0;
	ll iprod = 1;
	for(char c : str){
		int cc = c - '0';
		D.push_back(cc);
		isum += cc; 
		iprod *= (cc + 1);
	}
	dp[0][0][1][1] = 1;
	for(int i = 0; i < D.size(); i++) for(int j = 0; j < 150; j++) for(int k = 0; k < 3; k++) for(auto p : dp[i][j][k]){
		ll prod = p.first;
		ll num = p.second;
		for(int l = 0; l < 10; l++){
			//printf("%d %d %d %lld %lld %d\n", i, j, k, prod, num);
			if(k == 0 || (k == 1 && D[i] > l)) dp[i + 1][j + l][0][prod * (l + 1)] += num;
			if(k == 1 && D[i] == l)            dp[i + 1][j + l][1][prod * (l + 1)] += num;
			if(k == 2 || (k == 1 && D[i] < l)) dp[i + 1][j + l][2][prod * (l + 1)] += num;
		}
	}
	ll ans = 0;
	for(int j = 0; j < 150; j++) for(int k = 0; k < 3; k++) for(auto p : dp[D.size()][j][k]){
		ll prod = p.first;
		ll num = p.second;
		if(j < isum){
			ans += num;
		}else if(j == isum){
			if(prod < iprod){
				ans += num;
			}else if(prod == iprod){
				if(k == 0){
					ans += num;
				}
			}
		}
	}
	cout << ans << endl;
}