Problem: Example

Input

20


Output

4

Solution (in CPP):

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

int dp[2][140][20000][3],nxtind[20000][10];

signed main(){
	string s;
	cin >> s;
	int n = s.length(),sum = 0,prod = 1;
	for(int i = 0;i < n;i++){
		sum += s[i] - '0';
		prod *= s[i] - '0' + 1;
	}
	set<int> st;
	st.insert(1);
	for(int i = 0;i < n;i++){
		set<int> nxt;
		for(int v : st){
			for(int j = 1;j <= 10;j++) nxt.insert(v * j);
		}
		st.swap(nxt);
	}
	vector<int> vec(st.begin(),st.end());
	for(int i = 0;i < vec.size();i++){
		for(int j = 0;j < 10;j++){
			auto it = lower_bound(vec.begin(),vec.end(),vec[i] * (j + 1));
			if(*it == vec[i] * (j + 1)) nxtind[i][j] = it - vec.begin();
			else nxtind[i][j] = -1;
		}
	}
	dp[0][0][0][1] = 1;
	for(int i = 0;i < n;i++){
		int _i = i % 2;
		for(int j = 0;j <= (i + 1) * 9;j++){
			for(int k = 0;k < vec.size();k++){
				for(int l = 0;l < 3;l++) dp[!_i][j][k][l] = 0;
			}
		}
		for(int j = 0;j <= i * 9;j++){
			for(int k = 0;k < vec.size();k++){
				for(int l = 0;l < 10;l++){
					if(nxtind[k][l] == -1) continue;
					int dest;
					if(s[i] - '0' == l) dest = 1;
					else if(s[i] - '0' > l) dest = 0;
					else dest = 2;
					dp[!_i][j + l][nxtind[k][l]][dest] += dp[_i][j][k][1];
					dp[!_i][j + l][nxtind[k][l]][0] += dp[_i][j][k][0];
					dp[!_i][j + l][nxtind[k][l]][2] += dp[_i][j][k][2];
				}
			}
		}
	}
	int ans = 0,prodind = lower_bound(vec.begin(),vec.end(),prod) - vec.begin();
	for(int i = 0;i <= n * 9;i++){
		for(int j = 0;j < vec.size();j++){
			for(int k = 0;k < 3;k++){
				if(i < sum || (i == sum && j < prodind) || (i == sum && j == prodind && !k)) ans += dp[n % 2][i][j][k];
			}
		}
	}
	cout << ans << endl;
}