Problem: Example

Input

20


Output

4

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
#define int long long
using namespace std;

int n,sum,prod=1,dp1[210],cnt[20],pw[20],ans;
string s;
map<int,int> dp[20][210][2];

inline void dfs(int lvl,int num,int pro,int last)
{
	if(lvl==n+1){
		if(num!=sum) return;
		if(pro>=prod) return;
		int val=pw[n];
		for(int i=0;i<=9;i++) val/=pw[cnt[i]];
		ans+=val;
		return;
	}
	if(num>sum) return;
	if(num+(n-lvl+1)*9<sum) return;
	if(pro>=prod) return;
	for(int i=0;i<=9;i++){
		cnt[i]++;
		if(i>=last) dfs(lvl+1,num+i,pro*(i+1),i);
		cnt[i]--;
	}
}

inline int dfs2(int lvl,int num,int pro,bool flag)
{
	if(dp[lvl][num][flag].count(pro)){
		return dp[lvl][num][flag][pro];
	}
	if(lvl==n+1){
		if(num!=sum) return 0;
		if(pro!=prod) return 0;
		if(!flag) return 0;
		dp[lvl][num][flag][pro]=1;
		return 1;
	}
	if(num>sum) return 0;
	if(num+(n-lvl+1)*9<sum) return 0;
	if(prod%pro!=0) return 0;
	if(!flag){
		for(int i=0;i<=9;i++){
			if(i>(s[lvl-1]-'0')) continue;
			if(i==(s[lvl-1]-'0')) dp[lvl][num][flag][pro]+=dfs2(lvl+1,num+i,pro*(i+1),0);
			if(i<(s[lvl-1]-'0')) dp[lvl][num][flag][pro]+=dfs2(lvl+1,num+i,pro*(i+1),1);
		}
		return dp[lvl][num][flag][pro];
	}
	else{
		for(int i=0;i<=9;i++){
			dp[lvl][num][flag][pro]+=dfs2(lvl+1,num+i,pro*(i+1),1);
		}
		return dp[lvl][num][flag][pro];
	}
}

signed main()
{
	ios::sync_with_stdio(false);
	cin>>s;
	n=s.size();
	pw[0]=1;
	for(int i=1;i<=15;i++) pw[i]=pw[i-1]*i;
	//sum
	for(int i=1;i<=n;i++) sum+=(s[i-1]-'0');
	dp1[0]=1;
	for(int i=1;i<=n;i++){
		for(int j=sum;j>=0;j--){
			for(int k=1;k<=9;k++){
				if(j>=k) dp1[j]+=dp1[j-k];
			}
		}
	}
	for(int i=0;i<sum;i++) ans+=dp1[i];
	//prod
	for(int i=1;i<=n;i++) prod*=(s[i-1]-'0'+1);
	dfs(1,0,1,0);
	//int
	ans+=dfs2(1,0,1,0);
	cout<<ans<<endl;
	return 0;
}