Problem: Example

Input

20


Output

4

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
#define rdll(x) scanf("%lld",&x);
string str;
ll ans;
ll dp[205][15];
ll C[20][20];
ll calc(array<int,10>a){
	ll cc = 1;
	int zan = 0;
	rep(x,10){
		cc *= C[zan+a[x]][a[x]];
		zan += a[x];
	}
	return cc;
}
int main(){
	cin>>str;
	int sum = 0, n = str.size();
	ll M = 1;
	rep(i,n){
		sum += str[i]-'0';
		M *= (1+str[i]-'0');
	}
	dp[0][0] = 1;
	for(int j=0;j<n;j++){
		for(int i=0;i<150;i++){
			if(dp[i][j] == 0) continue;
			rep(x,10) dp[i+x][j+1] += dp[i][j];
		}
	}
	rep(i,20) rep(j,i+1) if(j==0||j==i)C[i][j]=1; else C[i][j]=C[i-1][j]+C[i-1][j-1];
	for(int S=0;S<sum;S++){
		ans += dp[S][n];
	}
	//sum ha equal
	int w = n+9;
	vector<pair<ll,array<int,10> > >hoge;
	rep(mask,(1<<w)){
		if(__builtin_popcount(mask) != 9) continue;
		int cur = 0;
		ll mul = 1;
		ll val = 1;
		int S = 0;
		array<int,10>num;
		rep(i,10) num[i] = 0;
		rep(i,w){
			if(((mask>>i)&1)){
				rep(u,cur){
					mul *= val;
					S += val-1;
				}
				num[val-1] = cur;
				val++;
				cur=0;
			}
			else cur++;
		}
		rep(u,cur){
			mul *= val;
			S += val-1;
		}
		if(S != sum) continue;
		if(mul > M) continue;
		num[val-1] = cur;
		hoge.pb(mp(mul,num));
	}
	vector<array<int,10> >same;
	for(int i=0;i<hoge.size();i++){
		if(hoge[i].fi > M) break;
		else if(hoge[i].fi < M){
			ll cc = 1;
			int zan = n;
			rep(x,10){
				cc *= C[zan][(hoge[i].sc)[x]];
				zan -= (hoge[i].sc)[x];
			}
			ans += cc;
		}
		else same.pb((hoge[i].sc));
	}
	for(int i=0;i<same.size();i++){
		array<int,10>zan = same[i];
		for(int j=0;j<str.size();j++){
			int x = str[j]-'0';
			for(int k=0;k<x;k++){
				if(zan[k] == 0) continue;
				zan[k]--;
				ans += calc(zan);
				zan[k]++;
			}
			if(zan[x] == 0) break;
			zan[x]--;
		}
	}
	cout<<ans<<endl;
}