Problem: Example

Input

20


Output

4

Solution (in CPP):

Solution:
#include<bits/stdc++.h>

#define rep(i,n) for(int i=0;i<(int)n;i++)
#define all(c) (c).begin(),(c).end()
#define mp make_pair
#define pb push_back
#define each(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
#define dbg(x) cerr<<__LINE__<<": "<<#x<<" = "<<(x)<<endl

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;
const int inf = (int)1e9;
const double INF = 1e12, EPS = 1e-9;

string s;
int d[14], n;
//ll dp[2][9*14+1][14*3+1][14*2+1][15][15][3];
unordered_map<ll, ll> dp[2][14*9+1][3];

int main(){
	cin >> s;
	n = s.size();
	rep(i, n) d[i] = s[i] - '0';
	
	int cur = 0, next = 1;
	dp[cur][0][1][1] = 1;
	rep(i, n){
		//rep(j, 14*9+1) rep(k, 3) dp[next][j][k].clear();
		rep(sum, 9*i+1) rep(sml, 3) for(auto p : dp[cur][sum][sml]){
			rep(x, 10){
				ll prod = p.first * (x + 1);
				int nsml = sml;
				if(sml == 1 && d[i] != x) nsml = d[i] > x ? 0 : 2;
				dp[next][sum + x][nsml][prod] += p.second;
			}
		}
		rep(sum, 9*i+1) rep(sml, 3) dp[cur][sum][sml].clear();
		swap(cur, next);
	}
	int dsum = 0;
	ll dprod = 1;
	ll ans = 0;
	rep(i, n) dsum += d[i], dprod *= d[i] + 1;
	rep(sum, dsum + 1) rep(sml, 3) for(auto p : dp[cur][sum][sml])
	if(sum < dsum || sum == dsum && p.first < dprod || sum == dsum && p.first == dprod && sml == 0){
		/*
		dbg(sum); dbg(dsum);
		dbg(p.first); dbg(dprod);
		dbg(sml); dbg(p.second);
		*/
		ans += p.second;
	}
	
	cout << ans << endl;
	return 0;
}