Problem: Example

Input

20


Output

4

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
using namespace std;
const int maxn=20;
char s[maxn];
typedef long long ll;
typedef pair<int,ll> pi;
ll f[maxn][maxn*10],P=1,ans=0,jc[maxn],xc[20][20];
int n,sum,c[maxn],a[maxn];
map<pi,ll> dp[20][2];
map<pi,ll> mp[20];
vector<pi> g[20];
ll calc(int n,int *a)
{
  ll res=jc[n];
  for(int i=0;i<=9;i++) res/=jc[a[i]];
  return res;
}
ll solve()
{
  ll res=0;
  for(int i=0;i<=9;i++) a[i]=c[i];
  for(int i=1;i<=n;i++)
  {
    for(int j=0;j<s[i]-'0';j++)
    {
	  if(!a[j]) continue;
      a[j]--;res+=calc(n-i,a);
      a[j]++;
    }
    if(a[s[i]-'0']) a[s[i]-'0']--;
    else break;
  }
  return res;
}
void dfs(int p,int num,int ns,ll np)
{
  if(ns>sum||P%np) return;
  if(p==9)
  {
	c[9]=n-num;
    if(ns+c[9]*9!=sum) return;
    np*=(ll)xc[9][c[9]];
    if(np==P) ans+=solve();
    return;
  }
  for(int i=0;i<=n-num;i++)
  {
	c[p]=i;dfs(p+1,num+i,ns+i*p,np*(ll)xc[p][i]);
  }
}
int main()
{
  scanf("%s",s+1);n=strlen(s+1);
  jc[0]=1;
  for(int i=1;i<=14;i++) jc[i]=jc[i-1]*i;
  for(int i=0;i<=9;i++) xc[i][0]=1;
  for(int i=0;i<=9;i++) for(int j=1;j<=14;j++) xc[i][j]=xc[i][j-1]*(ll)(i+1);
  for(int i=1;i<=n;i++) 
  {
    sum+=s[i]-'0';
    P*=(ll)(s[i]-'0'+1);
  }
  f[0][0]=1;
  for(int i=1;i<=n;i++)
    for(int k=0;k<=9;k++)
      for(int j=k;j<=sum;j++)
        f[i][j]+=f[i-1][j-k];
  for(int i=0;i<sum;i++) ans+=f[n][i];
  g[0].push_back((pi){0,1});
  mp[0][(pi){0,(ll)1}]=1;
  for(int i=0;i<n;i++)
    for(int l=0;l<g[i].size();l++)
    {
	  int ss=g[i][l].first;
      ll  pp=g[i][l].second;
      for(int j=0;j<=9;j++)
      {
	    int ns=ss+j;ll np=pp*(j+1);
        if(ns>sum||np>P) continue;
        if(!mp[i+1][(pi){ns,np}])
          g[i+1].push_back((pi){ns,np});
        mp[i+1][(pi){ns,np}]+=mp[i][g[i][l]];
      }
    }
  for(int i=0;i<g[n].size();i++)
  {
	int ss=g[n][i].first;ll pp=g[n][i].second;
    if(ss==sum&&pp<P) ans+=mp[n][g[n][i]];;
  }
  dfs(0,0,0,1);
  cout<<ans<<endl;
  return 0;
}