This problem asks to count integers constrained by their digits. For such problems, a kind of Dynamic Programming (DP) called digit DP is effective; indeed, this problem can be solved with digit DP too. (For details on digit DP, refer to other websites.)

The key to this problem is to fix the digit sum \(s\) first. That is, first solve the problem for each fixed \(s = 1, 2, \dots, 9 \times 14\), then the answer is found as the sum over all \(s\).
When \(s\) is fixed, the subproblem can be solved with DP whose states are defined by:

• \(dp_{d, i, j, f}\) \(:=\) (the number of ways to determine the \(d\) most significant digits of integers so that its digit sum is \(i\), its value modulo \(s\) is \(j\), and the determined digits equals those of \(N\) if \(f=0\) or less than those of \(N\) if \(f=1\)).

Denoting the \((d+1)\)-th digit by \(t\), the DP can be evaluated with transitions of distribution-DP type:

\[dp[d + 1][i + t][(10 j + t) \bmod s][(less than / equal)] \text{ += } dp[d][i][j][f].\]

(See also sample code.)

The complexity is \(\mathrm{O}((B \log N)^4)\), where \(B = 10\). (Here, \(\log N\) represents the number of digits in \(N\), so its base is \(10\); thus we have \((B \log_{10} N)^4 \leq (140)^4 \simeq 3.8 \times 10^8\). It is rather larger than usual, but with proper implementation it runs fast enough to fit in the time limit.)

• Sample code (C++)

#include <iostream>
#include <string>
#include <vector>
using namespace std;

#define rep(i, n) for (int i = 0; i < int(n); i++)

int main() {
  string N;
  cin >> N;
  long long ans = 0;
  for (int s = 1; s <= 9 * 14; s++) {
    vector dp(N.size() + 1, vector(s + 1, vector(s, vector(2, 0LL))));
    dp[0][0][0][1] = 1;
    rep(d, N.size()) rep(i, s + 1) rep(j, s) rep(f, 2) rep(t, 10) {
      if (i + t > s) continue;
      if (f and N[d] - '0' < t) continue;
      dp[d + 1][i + t][(j * 10 + t) % s][f and N[d] - '0' == t] += dp[d][i][j][f];
    }
    ans += dp[N.size()][s][0][0] + dp[N.size()][s][0][1];
  }
  cout << ans << endl;
}