Problem: Example

Input

20


Output

4

Solution (in CPP):

Solution:
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
using namespace std;
#define lld long long
const int N = 20;
int n,m;
lld tot=1;
lld f[N][N*N],A[N];
int use[N],nn[N];
char s[N];
lld ans;
lld pow(int a,int b)
{
    lld te = 1;
    for(int i = 1; i <= b; i++) te *= a;
    return te;
}
void solve()
{
    for(int i = 0; i < 10; i++) nn[i] = use[i];
    for(int i = 1; i <= n; i++)
    {
        lld te = 0;
        for(int j = 0; j < s[i]-'0'; j++)
            te += nn[j];
        te *= A[n-i];
        for(int j = 0; j <= 9; j++) te /= A[nn[j]];
        ans += te;
        if(!nn[s[i]-'0']) break;
        nn[s[i]-'0']--;
    }
}
void dfs(int a,int b,lld c,int e)
{
    if(c>tot || e>m) return;
    if(c*pow(a+1,n-b)>tot||e+a*(n-b)>m) return;
    if(e+9*(n-b)<m) return;
    if(b==n) {
        if(e==m) {

           // lld te = 1;
           // for(int i )
           //printf("%d\n",A[n]);

            if(c<tot) {
                lld ta = A[n];
                for(int i = 0; i <= 9; i++) ta /= A[use[i]];
                ans += ta;

            }
            else if(c==tot) solve();
        }
        return;
    }
    if(a==10) return;
    for(int i = 0; i <= n-b; i++)
    {
        use[a] = i;
        dfs(a+1,b+i,c*pow(a+1,i),e+a*i);
        use[a] = 0;
    }
}
int main()
{

    scanf("%s",s+1);
    n = strlen(s+1);
    A[0] = 1;
    for(int i = 1; i <= n; i++) {

        A[i] = A[i-1] * i;
        m += s[i] - '0';
        tot *= s[i] - '0' + 1;
    }

    f[0][0] = 1;
    for(int i = 1; i <= n; i++)
    for(int j = 0; j <= m; j++)
    for(int k = 0; k <= min(j,9); k++)
        f[i][j] += f[i-1][j-k];
    for(int i = 0; i < m; i++) ans += f[n][i];
    dfs(0,0,1,0);
    cout<<ans<<endl;
    return 0;
}