Problem: Example

Input

20


Output

4

Solution (in CPP):

Solution:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>

using namespace std;
typedef long long ll;
typedef pair<int, int> Pi;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define sz(x) (int)x.size()
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()

struct str{
	ll L1, L2, L3;
};

char A[15];
ll d1[15][150];
map <ll, str> M1[15][150];
int n;
ll powten[15];

void solve(int tc){
	scanf("%s", A);
	n = (int)strlen(A);
	int s = 0;
	for(int i=0;A[i];i++)s += A[i] - '0';
	ll mul = 1;
	for(int i=0;A[i];i++)mul *= (A[i] - '0' + 1);
	
	d1[0][0] = 1;
	for(int i=1;i<=n;i++){
		for(int j=0;j<10;j++){
			for(int k=0;k<=s-j;k++){
				d1[i][k+j] += d1[i-1][k];
			}
		}
	}
	ll ans = 0;
	for(int i=0;i<s;i++)ans += d1[n][i];
	
	for(int i=0;i<A[0]-'0';i++)M1[1][i][i+1] = str{1, 0, 0};
	M1[1][A[0]-'0'][A[0]-'0'+1] = str{0, 1, 0};
	for(int i=A[0]-'0'+1;i<10;i++)M1[1][i][i+1] = str{0, 0, 1};
	powten[0] = 1;
	for(int i=1;i<=14;i++)powten[i] = powten[i-1] * 10;
	
	for(int i=2;i<=n;i++){
		for(int j=0;j<10;j++){
			for(int u=0;u<=s-j;u++){
				for(map<ll, str>::iterator k=M1[i-1][u].begin(); k!=M1[i-1][u].end(); ++k){
					if(k->Fi * (j+1) > mul)break;
					if(k->Fi * (j+1) * powten[n-i] < mul){
						ans += (k->Se.L1 + k->Se.L2 + k->Se.L3) * d1[n-i][s-u-j];
						continue;
					}
					
					str x = M1[i-1][u][k->Fi];
					M1[i][u+j][(j+1)*k->Fi].L1 += x.L1;
					M1[i][u+j][(j+1)*k->Fi].L3 += x.L3;
					if(j < A[i-1]-'0')M1[i][u+j][(j+1)*k->Fi].L1 += x.L2;
					else if(j == A[i-1]-'0')M1[i][u+j][(j+1)*k->Fi].L2 += x.L2;
					else M1[i][u+j][(j+1)*k->Fi].L3 += x.L2;
				}
			}
		}
		for(int j=0;j<=s;j++)M1[i-1][j].clear();
	}
	ans += M1[n][s][mul].L1;
	printf("%lld\n", ans);
}

int main(){
	int Tc = 1;// scanf("%d",&Tc);
	for(int i=1;i<=Tc;i++){
		solve(i);
	}
	return 0;
}