Problem: Example

Input

20


Output

4

Solution (in CPP):

Solution:
#include <iostream>
#include <vector>
#include <string>

using namespace std;

long long fact[15];

vector< vector<int> > digits;

void search(vector<int>& v, int cur, int rest){
	if(cur == 9){
		v[cur] = rest;
		digits.push_back(v);
		return;
	}
	for(int i=0;i<=rest;i++){
		v[cur] = i;
		search(v, cur+1, rest-i);
	}
}

long long perm(const vector<int>& v){
	int sum = 0;
	for(int i=0;i<10;++i) sum += v[i];
	long long res = fact[sum];
	for(int i=0;i<10;i++) res /= fact[v[i]];
	return res;
}

int main(){
	fact[0] = 1;
	for(int i=1;i<=14;i++) fact[i] = i * fact[i-1];
	string S;
	while(cin >> S){
		int n = S.size();
		digits.clear();
		vector<int> v(10, 0);
		search(v, 0, n);
		int sum = 0;
		long long prod = 1;
		for(int i=0;i<n;i++){
			sum += S[i] - '0';
			prod *= S[i] - '0' + 1;
		}
		long long res = 0;
		for(const vector<int>& dig : digits){
			v = dig;
			int s = 0;
			long long p = 1;
			for(int i=0;i<10;i++){
				s += i*v[i];
				for(int j=0;j<v[i];j++) p *= i+1;
			}
			if(s < sum || (s == sum && p < prod)){
				res += perm(v);
			} else if(s == sum && p == prod) {
				for(int i=0;i<n;i++){
					for(int j=0;j<S[i]-'0';j++){
						if(v[j] == 0) continue;
						--v[j];
						res += perm(v);
						++v[j];
					}
					if(v[S[i]-'0'] == 0) break;
					--v[S[i]-'0'];
				}
			}
		}
		cout << res << endl;
	}
}