Problem: Example

Input

20


Output

4

Solution (in CPP):

Solution:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define LL long long
int a[10],b[10],n,Sum=0;
LL jc[15],Pro=1,ans=0;
char s[20];
LL cal(int n)
{
    int i;LL ans=jc[n]; 
    for (i=0;i<=9;i++) ans/=jc[b[i]];
    return ans;
}
LL cal0()
{
    for (int i=0;i<=9;i++) b[i]=a[i];
    return cal(n);
}
LL cal1()
{
    int i,j;LL ans=0;
    for (i=0;i<=9;i++) b[i]=a[i];
    for (i=1;i<n;i++)
    {
        for (j=0;j<s[i]-'0';j++) if (b[j]) {b[j]--;ans+=cal(n-i);b[j]++;}
        if (b[s[i]-'0']) b[s[i]-'0']--; else break;
    }
    return ans;
}
void dfs(int x,int num,int sum,LL pro)
{
    if (sum>Sum||sum==Sum&&pro>Pro) return;
    if (x==n)
    {
        if (sum<Sum||sum==Sum&&pro<Pro) ans+=cal0();
         else ans+=cal1();
        return;
    }
    for (int j=num;j<=9;j++) {a[j]++;dfs(x+1,j,sum+j,pro*((LL)(j+1)));a[j]--;}
}
int main()
{
  //  freopen("in.txt","r",stdin);freopen("out.txt","w",stdout);
    scanf("%s",s+1);n=strlen(s+1);jc[0]=1;
    for (int i=1;i<=n;i++) {Sum+=s[i]-'0';Pro*=(LL)(s[i]-'0'+1);jc[i]=jc[i-1]*((LL)i);}
    for (int i=0;i<=9;i++) {a[i]++;dfs(1,i,i,i+1);a[i]--;}
    printf("%lld\n",ans);
    
    return 0;
}