Problem: Example

Input

20


Output

4

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
#define MOD 1000000007LL
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<P,P> PP;
string d;
int len;
ll dp[15][150];
ll tenval[15];
int sum=0;
ll prod=1;
map<PP,ll> mp;

ll dfs(int v,int nsum,ll nowp,int flag){
	if(nsum>sum || nsum+(len-v)*9<sum)return 0;
	if(v==len){
		if(nowp<prod)return 1;
		if(nowp==prod && flag==2)return 1;
		return 0;
	}
	if(flag==2 && nowp*tenval[v]<=prod){
		return dp[len-v][sum-nsum];
	}
	if(flag<=1 && nowp*tenval[v]<prod){
		return dp[len-v][sum-nsum];
	}
	if(mp.find(PP(P(v,nsum),P(nowp,flag)))!=mp.end()){
		return mp[PP(P(v,nsum),P(nowp,flag))];
	}
	ll tp=0;
	for(int i=0;i<=9;i++){
		if((ll)nowp*i>prod)break;
		int nv=flag;
		if(flag==0){
			if(i>(d[v]-'0'))nv=1;
			if(i<(d[v]-'0'))nv=2;
		}
		tp+=dfs(v+1,nsum+i,(ll)nowp*(i+1),nv);
	}
	return mp[PP(P(v,nsum),P(nowp,flag))]=tp;
}

int main(void){
	cin >> d;
	ll ans=0;
	len=d.size();
	for(int i=0;i<len;i++){
		sum+=(d[i]-'0');
		prod=(ll)prod*((d[i]-'0')+1);
	}
	dp[0][0]=1;
	for(int i=0;i<len;i++){
		for(int j=0;j<=i*10;j++){
			for(int k=0;k<=9;k++){
				dp[i+1][j+k]+=dp[i][j];
			}
		}
	}
	for(int i=0;i<sum;i++){
		ans+=dp[len][i];
	}
	tenval[len]=1;
	for(int i=len-1;i>=0;i--){
		tenval[i]=tenval[i+1]*10LL;
	}
	ans+=dfs(0,0,1,0);
	printf("%lld\n",ans);
	return 0;
}