Problem: Example

Input

20


Output

4

Solution (in CPP):

Solution:
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define LL long long 
#define N 18600
bool a[43][29][29][15];
LL f[16][43][29][29][15],state[N+20],n,ans;
int num,trans[N][10],len,all;char s[233];
LL dp[2][127][N+10][3];
void pre_work(){
	f[0][0][0][0][0]=1;
	for(int i=0;i<=14;i++)
		for(int j=0;j<=42;j++)
			for(int k=0;k<=28;k++)
				for(int l=0;l<=28;l++)
					for(int m=0;m<=14;m++)
						if(f[i][j][k][l][m]!=0){
							if(!a[j][k][l][m])a[j][k][l][m]=true,state[++num]=f[i][j][k][l][m];
							if(i==14)continue;
							for(int n=2;n<=10;n++)
								if(n==1)f[i+1][j][k][l][m]=f[i][j][k][l][m]*1;
								else if(n==2)f[i+1][j+1][k][l][m]=f[i][j][k][l][m]*2;
								else if(n==3)f[i+1][j][k+1][l][m]=f[i][j][k][l][m]*3;
								else if(n==4)f[i+1][j+2][k][l][m]=f[i][j][k][l][m]*4;
								else if(n==5)f[i+1][j][k][l+1][m]=f[i][j][k][l][m]*5;
								else if(n==6)f[i+1][j+1][k+1][l][m]=f[i][j][k][l][m]*6;
								else if(n==7)f[i+1][j][k][l][m+1]=f[i][j][k][l][m]*7;
								else if(n==8)f[i+1][j+3][k][l][m]=f[i][j][k][l][m]*8;
								else if(n==9)f[i+1][j][k+2][l][m]=f[i][j][k][l][m]*9;
								else if(n==10)f[i+1][j+1][k][l+1][m]=f[i][j][k][l][m]*10;
							}
	sort(state+1,state+num+1);
	for(int i=1;i<=N;i++){
		LL now=state[i];
		for(int j=0;j<=9;j++){
			LL to=state[i]*(j+1);
			int pos=lower_bound(state+1,state+num+1,to)-state;
			if(state[pos]==to)trans[i][j]=pos;
			else trans[i][j]=0;
		}
	}
}
int main(){
	pre_work();
	scanf("%s",s);len=strlen(s);n=1;
	for(int i=0;i<len;i++)n=n*(s[i]-'0'+1),all=all+(s[i]-'0');
	dp[0][0][1][1]=1;
	for(int i=0;i<len;i++){
		int now=i&1,to=now^1,sum=min(all,(i+1)*9);
		memset(dp[to],0,sizeof(dp[to]));
		for(int j=0;j<=sum;j++)
			for(int k=1;k<=N;k++){
				if(dp[now][j][k][0]){
					for(int l=0;l<=9;l++)
						dp[to][j+l][trans[k][l]][0]+=dp[now][j][k][0];
				}
				if(dp[now][j][k][1]){
					for(int l=0;l<s[i]-'0';l++)
						dp[to][j+l][trans[k][l]][0]+=dp[now][j][k][1];
					int r=s[i]-'0';
					dp[to][j+r][trans[k][r]][1]+=dp[now][j][k][1];
					for(int l=s[i]-'0'+1;l<=9;l++){
						dp[to][j+l][trans[k][l]][2]+=dp[now][j][k][1];
					}
				}
				if(dp[now][j][k][2]){
					for(int l=0;l<=9;l++)
						dp[to][j+l][trans[k][l]][2]+=dp[now][j][k][2];
				}
			}
	}
	int now=len&1,pos=lower_bound(state+1,state+num+1,n)-state;
	for(int i=0;i<all;i++)
		for(int j=1;j<=N;j++)
			for(int k=0;k<=2;k++)
				ans+=dp[now][i][j][k];
	for(int i=all;i<=all;i++)
		for(int j=1;j<pos;j++)
			for(int k=0;k<=2;k++)
				ans+=dp[now][i][j][k];
	for(int i=all;i<=all;i++)
		for(int j=pos;j<=pos;j++)
			for(int k=0;k<1;k++)
				ans+=dp[now][i][j][k];
	printf("%lld\n",ans);
	return 0;
}