Problem: Example

Input

20


Output

4

Solution (in CPP):

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

const int maxn = 20; 

typedef long long ll; 

int n, SUM;
int d[maxn];
ll C[maxn][maxn]; 
ll Pow[maxn][maxn]; 
ll ans, PROD; 
int a[maxn]; 
int b[maxn]; 
/*
void solve1() {
	memset( f, 0, sizeof( f ) ); 
	f[0][0] = 1; 
	for (int i = 1; i <= n; ++i) 
		for (int j = 0; j <= n * 9; ++j) 
			for (int k = 0; k <= min(j,9); ++k) 
				f[i][j] += f[i-1][j-k];
	for (int i = 0; i < SUM; ++i) ans += f[n][SUM]; 
}*/

ll Count() {
	//cout<<b[0]<<' '<<b[1]<<' '<<b[2]<<endl; 
	int all = 0; 
	ll ret = 1; 
	for (int i = 0; i <= 9; ++i) {
		if ( b[i] < 0 ) return 0; 
		all += b[i]; 
		ret *= C[all][b[i]]; 
	}
	return ret; 
}

void dfs(int dep, int left, int sum, ll prod) {
	if ( dep > 9 ) {
		if ( left == 0 ) {
			for (int i = 0; i <= 9; ++i) b[i] = a[i]; 
			if ( sum < SUM || prod < PROD ) ans += Count(); 
			else if ( prod == PROD ) {
				for (int i = 1; i <= n; ++i) {
					if ( i != 1 ) b[d[i-1]]--;
					for (int j = 0; j < d[i]; ++j) {
						b[j]--; 
						ans += Count(); 
						b[j]++; 
					}
				} 
			}
		}
		return; 
	}
	for (int i = 0; i <= left; ++i) 
		if ( i * dep + sum <= SUM ) {//&& prod*Pow[i+1][dep] <= PROD ) {
			a[dep] = i; 
			dfs( dep+1, left-i, sum+i*dep, prod*Pow[dep+1][i] );
		}
}

void Init() {
	memset( C, 0, sizeof( C ) ); 
	C[0][0] = 1; 
	for (int i = 1; i <= n; ++i) {
		C[i][0] = 1; 
		for (int j = 1; j <= n; ++j) C[i][j] = C[i-1][j-1] + C[i-1][j]; 
	}
	for (int i = 1; i <= 10; ++i) {
		Pow[i][0] = 1; 
		for (int j = 1; j <= n; ++j)
			Pow[i][j] = Pow[i][j-1] * i; 
	}
}

int main() {
	char st[maxn]; 
	cin>>st; 
	n = strlen( st ); 
	for (int i = 1; i <= n; ++i) d[i] = st[i-1] - '0'; 
	SUM = 0; 
	for (int i = 1; i <= n; ++i) SUM += d[i]; 
	PROD = 1;
	for (int i = 1; i <= n; ++i) PROD *= ( d[i] + 1 ); 
	Init(); 
	ans = 0;
	dfs( 0, n, 0, 1 ); 
	cout<<ans<<endl; 
}