Problem: Example

Input

20


Output

4

Solution (in CPP):

Solution:
#include<iostream>
#include<algorithm>
using namespace std;
long ans;
string s;
int n,sum;
long fac[15],prod=1;
long power(long a,long b){return b?power(a*a,b/2)*(b%2?a:1):1;}
int cnt[10];
void dfs(int p,int c)
{
	if(p<10)
	{
		for(int i=0;i<=c;i++)
		{
			cnt[p]=i;
			dfs(p+1,c-i);
		}
		cnt[p]=0;
		return;
	}
	if(c)return;
	int nowsum=0;
	long nowprod=1;
	for(int i=0;i<10;i++)
	{
		nowsum+=i*cnt[i];
		nowprod*=power(i+1,cnt[i]);
	}
	if(nowsum<sum||nowsum==sum&&nowprod<prod)
	{
		long plus=fac[n];
		for(int i=0;i<10;i++)plus/=fac[cnt[i]];
		ans+=plus;
		return;
	}
	else if(!(nowsum==sum&&nowprod==prod))return;
	int sto[10]={};
	for(int i=0;i<10;i++)sto[i]=cnt[i];
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<s[i]-48;j++)
		{
			if(cnt[j]==0)continue;
			long now=fac[n-i-1];
			cnt[j]--;
			for(int k=0;k<10;k++)now/=fac[cnt[k]];
			ans+=now;
			cnt[j]++;
		}
		if(cnt[s[i]-48]==0)break;
		cnt[s[i]-48]--;
	}
	for(int i=0;i<10;i++)cnt[i]=sto[i];
}
int main()
{
	cin>>s;
	n=s.size();
	fac[0]=1;
	for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i;
	for(int i=0;i<n;i++)
	{
		sum+=s[i]-48;
		prod*=s[i]-47;
	}
	dfs(0,n);
	cout<<ans<<endl;
}