Problem: Example

Input

20


Output

4

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
using namespace std;
typedef long long int64;
string S;
map< tuple< int, int, int64, int >, int64 > dp;
int length;
int64 weight;

int64 dfs(int idx, int num, int64 seki, int flag)
{
  if(num - (length - idx) * 9 > 0) return(0);
  if(idx == length) {
    if(seki != weight) return(seki < weight);
    return(flag == 1);
  }
  if(dp.find(make_tuple(idx, num, seki, flag)) != dp.end()) return(dp[make_tuple(idx, num, seki, flag)]);
  int64 ret = 0;
  for(int i = 0; i <= min(num, 9); i++) {
    int nextflag = flag;
    if(flag == 0) {
      if(i < S[idx] - '0')      nextflag = 1;
      else if(i > S[idx] - '0') nextflag = 2;
    }
    ret += dfs(idx + 1, num - i, seki * (i + 1), nextflag);
  }
  return(dp[make_tuple(idx, num, seki, flag)] = ret);
}

int main()
{
  cin >> S;
  length = S.size();
  int sum = accumulate(S.begin(), S.end(), 0) - '0' * S.size();
  if(sum == 0) {
    cout << 0 << endl;
  } else {
    vector< int64 > poyo(sum, 0);
    poyo[0] = 1;
    for(int i = 0; i < length; i++) {
      for(int j = sum - 1; j >= 0; j--) {
        for(int k = j + 1; k <= min(sum - 1, j + 9); k++) {
          poyo[k] += poyo[j];
        }
      }
    }
    weight = 1;
    for(int i = 0; i < S.size(); i++) weight *= (S[i] - '0' + 1);
    cout << accumulate(poyo.begin(), poyo.end(), 0LL) + dfs(0, sum, 1, 0) << endl;
  }
}