Problem: Example

Input

20


Output

4

Solution (in CPP):

Solution:
//by xxj
#include<bits/stdc++.h>
using namespace std;
#define fst first
#define snd second
#define mp make_pair
#define ll long long
#define pii pair<int,int>
#define lowbit(x) x&-x
const int inf=1e9+7;
const double eps=1e-10;
const ll linf=1e18+7;
const ll hh=523;
//const int mod=;
string s;
ll dps[17][127];
ll dpp[2][127][43][29][15][15];
ll ans;
int j2=0,j3=0,j5=0,j7=0;
int n;
int hve[17];
int c[17][17];
vector<int> v[17];
ll nw=1,prod=1;
bool used[10007];
void init2(){
	c[0][0]=1;
	for (int i=1;i<=14;i++){
		c[i][0]=1;
		for (int j=1;j<=i;j++){
			c[i][j]=c[i-1][j-1]+c[i-1][j];
		}
	}
}
ll calc(){
	int t=n;
	ll re=1;
	for (int i=0;i<=9;i++){
		re*=c[t][hve[i]];
		t-=hve[i];
//		cout<<hve[i]<<' ';
	}
//	puts("");
//	cout<<n<<' '<<t<<endl;
	return re;
}
void go(int k,int sum,int h){
	if (k*9<sum){
		return;
	}
	if (k==0){
//		int t=calc();
//		cout<<calc()<<endl;
//		cout<<sum<<' '<<nw<<endl;
		if (nw<prod){
			ans+=calc();
		}
		if (nw==prod){
			for (int i=0;i<=9;i++){
				v[i].push_back(hve[i]);
//				cout<<hve[i]<<' ';
			}
//			puts("");
		}
		return;
	}
	for (int i=h;i<=min(sum,9);i++){
		hve[i]++;
		nw*=(i+1);
		if (nw>prod){
			hve[i]--;
			nw/=(i+1);
			break;
		}
		go(k-1,sum-i,i);
		hve[i]--;
		nw/=(i+1);
	}
}
ll calc2(int k,int cs){
//	puts("in");
	ll re=1;
	int t=n-cs;
//	cout<<t<<endl;
	for (int i=0;i<=9;i++){
//		cout<<v[i][k]<<' ';
		re*=c[t][v[i][k]];
		t-=v[i][k];
//		cout<<v[k][i]<<' ';
	}
//	puts("out");
	return re;
}
int main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
//	init();
//	puts("!!!");
	init2();
	cin>>s;
//	puts("!!");
	dps[0][0]=1;
	for (int i=1;i<=14;i++){
		for (int j=0;j<=9*i;j++){
//			cout<<i<<' '<<j<<endl;
			for (int k=0;k<=min(j,9);k++){
				dps[i][j]+=dps[i-1][j-k];
			}
		}
	}
	int sum=0;
	n=s.size();
	for (int i=0;i<n;i++){
		sum+=(s[i]-'0');
		prod*=(s[i]-'0')+1;
	}
	for (int i=0;i<sum;i++){
		ans+=dps[n][i];
	}
//	cout<<prod<<endl;
//	cout<<ans<<endl;
	go(n,sum,0);
//	cout<<ans<<endl;
	int cnt=v[0].size();
//	cout<<cnt<<endl;
//	for (int j=0;j<=9;j++){
//		cout<<v[j][0]<<' ';
//	}
//	puts("");
	for (int i=0;i<n-1;i++){
//		cout<<i<<endl;
		for (int k=0;k<cnt;k++){
			if (used[k]){
				continue;
			}
//			cout<<k<<endl;
			for (int j=0;j<(s[i]-'0');j++){
//				cout<<j<<endl;
				if (!v[j][k]){
					continue;
				}
//				cout<<j<<endl;
				v[j][k]--;
				ans+=calc2(k,i+1);
//				cout<<ans<<endl;
				v[j][k]++;
			}
			if (v[s[i]-'0'][k]){
				v[s[i]-'0'][k]--;
			}
			else{
				used[k]=true;
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}
/*
input:
2034->641
*/