以下のように定義します。

\(A_{N,M}\) を問題の答えとする。
\(D_{N,M} = A_{N,M} - A_{N-1,M}\) とする。
\(\displaystyle f_N(x) = \sum_{M} \frac{D_{N,M}}{M!} x^M\) とする。

ちょうど \(N\) 桁の数について考えると以下のようになります。ただし、最高位は \(1 \sim 9\) しかとらないことに注意してください。

\[\displaystyle f_N(x) = \sum_{M} \sum_{1 \le d_0 \le 9, 0 \le d_1, \dots , d_{N-1} \le 9} \frac{(d_0 10^0 + d_1 10^1 + \cdots + d_{N-1} 10^{N-1})^M}{M!} x^M\]

整理すると

\[\displaystyle f_N(x) = \sum_{1 \le d_0 \le 9, 0 \le d_1, \dots , d_{N-1} \le 9} \exp ( (d_0 10^0 + d_1 10^1 + \cdots + d_{N-1} 10^{N-1}) x )\]

\[=\sum_{1 \le d_0 \le 9, 0 \le d_1, \dots , d_{N-1} \le 9} \left( \prod_{0 \le i \le N-1} \exp(d_i10^i x) \right)\]

\[ = \left( \sum_{1 \le d \le 9} \exp(d x) \right) \prod_{1 \le i \le N-1} \left( \sum_{0 \le d \le 9} \exp(d10^i x) \right)\]

\[ = \frac{(\exp(10x) - \exp(x))(\exp(10^Nx) - 1)}{(\exp(x) - 1)(\exp(10x)-1)}\]

これを足し合わせます。

\[\displaystyle A_{N,M} = M! [x^M]\frac{(\exp(10x) - \exp(x)) \displaystyle \sum_{1 \le i \le N}(\exp(10^ix) - 1)}{(\exp(x) - 1)(\exp(10x)-1)}\]

それぞれの分母・分子のそれぞれの項（計 \(4\) つ）を \(O(M)\) 項計算すればよいです。計算量は \(O(M (\log M + \log N))\) です。