Problem: Example

Input

20


Output

4

Solution (in CPP):

Solution:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N=15;
LL n,m,z,x,y,len,ans,sum,f[N][127],cj,a[10],jc[N],cf[11][N];
char s[15];
void work1(){
	for (int i=0;i<len;++i) sum+=s[i]-'0';
	f[0][0]=1;
	for (int i=1;i<=len;++i)
	for (int j=0;j<sum;++j)
	for (int k=0;k<=9;++k)
	if (j>=k) f[i][j]+=f[i-1][j-k];
	for (int i=0;i<sum;++i) ans+=f[len][i];
}
LL calc(){
	LL ans=1,tot=0;
	for (int i=0;i<=9;++i) tot+=a[i];
	ans*=jc[tot];
	for (int i=0;i<=9;++i) ans/=jc[a[i]];
	return ans;
}
void work3(){
	LL b[10];
	memcpy(b,a,sizeof(a));
	for (int i=1;i<=len;++i){
		for (int j=0;j<s[i-1]-'0';++j)
		if (a[j]!=0){
			--a[j];ans+=calc();++a[j];
		}
		if (a[s[i-1]-'0']!=0) --a[s[i-1]-'0'];
		else break;
	}
	memcpy(a,b,sizeof(a));
}
void dfs(int w,int now,int Sum,LL nowj){
	if (w==9){
		a[9]=len-now;
		if (Sum+a[9]*9!=sum) return;
		if (nowj*cf[10][a[9]]>cj) return;
		if (nowj*cf[10][a[9]]==cj){
			work3();return;
		}
		ans+=calc();
		return;
	}
	if (Sum+w*(len-now)>sum) return;
	for (int i=0;i<=len-now;++i)
	if (nowj*cf[w+1][i]<=cj && Sum+w*i<=sum) {
		a[w]=i;
		dfs(w+1,now+i,Sum+w*i,nowj*cf[w+1][i]);
	}
}
void work2(){
	cj=1;
	for (int i=0;i<len;++i) cj*=s[i]-'0'+1;
	dfs(0,0,0,1);
}
int main(){
	scanf("%s",s);
	len=strlen(s);
	jc[0]=1;
	for (int i=1;i<=14;++i) jc[i]=jc[i-1]*i;
	for (int i=1;i<=10;++i) cf[i][0]=1;
	for (int i=1;i<=10;++i)
	for (int j=1;j<=14;++j) cf[i][j]=cf[i][j-1]*i;
	work1();
	work2();
	cout<<ans<<endl;
}