Problem: Example

Input

20


Output

4

Solution (in CPP):

Solution:
#include <iostream>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <cstdio>
#include <vector>
#include <set>
#include <cassert>
#include <cstdlib>
#include <complex>
#include <cctype>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <functional>
#include <iomanip>
//#include <windows.h>  //Should be deleted when using AtCoder&POJ
using namespace std;

#define ll long long
#define pii pair<int,int>
#define qi ios::sync_with_stdio(0)
/**==Info==
*Program:1
*Problem:Bringing Order To Disorder
*Date:2019-7-5
*Algorithm:My Rubbish DP that will TLE 
*Stats:AC-Aaizu1360*/

bool debug=false;

map<ll,ll> dp[15][150][3];

const int LIMITED=1,FREE=0,EXCEED=2;
string s;

int allSum;
ll allPro;

ll dfs(int pos,int sum,ll pro,int limit){
	
//	cout<<pos<<" "<<sum<<" "<<pro<<" "<<limit<<endl;
	
//	cout<<"Compare with "<<allSum<<" "<<allPro<<endl;
	
	
	if(sum>allSum){
		return 0;
	}
	if(sum==allSum && pro>allPro){
		return 0;
	}
	if(sum==allSum && pro==allPro && limit==EXCEED){
		return 0;
	}
	if(dp[pos][sum][limit].count(pro)){
		return dp[pos][sum][limit][pro];
	}
//	cout<<"PTP"<<endl;
	
	if(pos==s.size()){
		
//		cout<<"Note:Good"<<endl;
		if(sum<allSum){
			return 1;
		}
		if(sum==allSum && pro<allPro){
			return 1;
		}
//		cout<<"Answer accept protect failed"<<endl;
		if(sum==allSum && pro==allPro){
			
			return !limit;
		}
		return 0;
	}
	
	ll poss=0;
	for(int i=0;i<=9;i++){
//		cout<<"Choosing "<<i<<endl;
//		cout<<"{"<<endl;
		poss+=dfs(pos+1,sum+i,pro*(i+1),(limit==EXCEED?EXCEED:(limit==LIMITED?(i==s[pos]-'0'?LIMITED:(i>s[pos]-'0'?EXCEED:FREE)):FREE)));
//		cout<<"}"<<endl;
	}
	
	return dp[pos][sum][limit][pro]=poss;
}

int main(int argc,char* argv[]){
	cin>>s;
	
	for(int i=0;i<s.size();i++){
		allSum+=s[i]-'0';
	}
	
	allPro=1;
	for(int i=0;i<s.size();i++){
		allPro*=(s[i]-'0'+1);
	}
	
	cout<<dfs(0,0,1,LIMITED)<<endl;
	return 0;
}