Problem: Example

Input

20


Output

4

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
#define ms(x,y) memset(x,y,sizeof(x))
#define ll long long 
using namespace std;


int a[20],b[20],len;
ll n,f[20][205];
ll ans;
ll nprod;
int c[20];
ll fact[20];

void calc2(int len){
	ll tmpans=fact[len];
	for(int i=0;i<=9;i++)
		tmpans/=fact[c[i]];
	ans+=tmpans;
}

void calc(){
	int i;
	for(i=1;i<=len;i++){
		for(int j=0;j<a[i];j++){
			if(c[j]!=0){
				c[j]--;
				calc2(len-i);
				c[j]++;
			}
		}
		if(c[a[i]]!=0)
			c[a[i]]--;
		else break;
	}
	for(i=i-1;i>=1;i--)c[a[i]]++;
}


void dfs(int now,int lim,int sum,ll prod){
	if(now==10){
		if(lim==0 && sum==0){
			if(prod==nprod)calc();
			else calc2(len);
		}
		return;
	}
	for(int i=0;i<=lim && now*i<=sum && prod<=nprod;i++,prod*=now+1){
		c[now]=i;
		dfs(now+1,lim-i,sum-now*i,prod);
	}
}

int main(){
	char ch[20];
	scanf("%s",ch+1);
	len=strlen(ch+1);
	for(int i=1;i<=len;i++)
		a[i]=ch[i]-'0';
	int sum=0;
	nprod=1;
	for(int i=1;i<=len;i++){
		sum+=a[i];
		nprod*=a[i]+1;
	}
	fact[0]=1;
	for(int i=1;i<=14;i++)
		fact[i]=fact[i-1]*i;

	ans=0;
	//calc
	ms(f,0);f[0][0]=1;
	for(int i=1;i<=len;i++)
		for(int nu=0;nu<=9;nu++)
			for(int k=nu;k<=sum;k++)
				f[i][k]+=f[i-1][k-nu];
	for(int i=0;i<sum;i++)
		ans+=f[len][i];
	
	dfs(0,len,sum,1);

	cout<<ans<<endl;
	return 0;
}