Let \(n\) be the number of digits of \(N\).
We use the following Dynamic Programming (DP).
\(\mathrm{dp}[i][j]\): The number of combination of the most significant \(i\) digits such that

• strictly less than the most significant \(i\) digits of \(N\),
• not all digits are \(0\), and
• there are \(j\) distinct digits, except for the leading \(0\)s.

From \(\mathrm{dp}[i][j]\), we have the following transitions:

• If we use any of \(j\) digits used so far for the \(i + 1\)-th significant digit: add \(\mathrm{dp}[i][j] \times j\) to \(\mathrm{dp}[i + 1][j]\)
• If we use a digit other than \(j\) digits used so far for the \(i + 1\)-th significant digit: add \(\mathrm{dp}[i][j] \times (16 - j)\) to \(\mathrm{dp}[i + 1][j + 1]\)

By the definition of \(\mathrm{dp}[i][j]\), we know that it is already strictly less than \(N\), so no matter what digit we choose, the most significant \(i + 1\) digits we obtain is less than the most significant \(i +1\) digits of \(N\).
Also, other than them, we have to process those which is not contained in \(\mathrm{dp}[i]\) but affects \(\mathrm{dp}[i + 1]\).

• If the most significant \(N\) digits is equal to those of \(N\)
  The most significant \(i + 1\) digits should be less than the most significant \(i + 1\) digits of \(N\)
  Since the most significant \(i\) digits is equal to those of \(N\), it is easy to find the set of the digits used so far, and therefore we can find the number of combinations of the \(i + 1\) digits after transition
  
• If the first \(i\) digits are all \(0\)
  That is, the \(i + 1\)-th digit is the first appearance of non-zero digit
  Since the most significant digit of \(N\) is non-zero, the resulting \(i + 1\) digits is always less than the most significant \(i + 1\) digits of \(N\), no matter which of \(15\) kinds of digits is used for the \(i + 1\)-th digit
  Therefore, we can add \(15\) to \(\mathrm{dp}[i + 1][1]\)

\(\mathrm{dp}[n][K]\) is the number of those integers less than \(N\) that satisfies the conditions given in the problem statement, so if we additionally process those which are equal to \(N\), we can easily find the answer.

With a proper implementation, the time complexity is \(O(nd) = O(\log(N)d)\), where \(d\) is the radix (\(= 16\) in this problem).

This solution is originally by kyopro_friends. Thank you.