Reinterpreting the problem

The following relation holds. Here, a power of \(10\) with \(c\) digits is defined as the integer \(10^{d-1}\).

An \(n\) integer can be represented as the sum of \(N\) repunits with \(M\) digits or less \(\iff\) \(\frac{9n + N}{10}\) can be represented as the sum of \(N\) powers of \(10\) with \(M\) digits or less.

Both \(\implies\) and \(\impliedby\) can be easily shown by corresponding the \(d\)-digit repunit with the \(d\)-digit power of \(10\).

Therefore, the problem is reduced as follows:

Find the number, modulo \(998244353\), of integers that can be represented as the sum of \(N\) powers of \(10\) with \(M\) digits or less.

From now on, we will consider this reduced version.

Decision problem

Given an integer \(n\), let us consider whether \(n\) can be represented as the sum of \(N\) powers of \(10\) with \(M\) digits or less.

First, when we represent \(n\) as the sum of powers of \(10\), consider how we can minimize the number of powers of \(10\). The following greedy algorithm is valid:

For \(i = M - 1, M - 2, \ldots, 1, 0\) in order, do the following:

• Let \(Q\) and \(R\) be the quotient and remainder when \(n\) is divided by \(10^i\), respectively. Decide to use \(Q\) copies of \(10^i\), and replace \(n\) with \(R\).

Let \(f(n)\) be the minimum number of powers of \(10\) when representing \(n\) as powers of \(10\) with \(M\) digits or less. To get straight to the point, \(n\) can be represented as the sum of \(N\) powers of \(10\) with \(M\) digits or less if and only if:

• \(n \geq N\)
• \(f(n) \leq N\)
• \(f(n) \equiv N \pmod 9\)

The first condition is necessary because powers of \(10\) are positive integers; the second by definition of \(f(n)\); the third follows from the condition when the sum is divided by \(9\). Meanwhile, these conditions are sufficient because, for \(10^{d_1} + 10^{d_2} \ldots + 10^{d_{f(n)}} = n\), one can choose \(i\) with \(d_i > 0\) and replace \(10^{d_i}\) with ten copies of \(10^{d_i - 1}\), and performing this \(\frac{N - f(n)}{9}\) times yields a representation of \(n\) as the sum of \(N\) powers of \(10\) with \(M\) digits or less. Note that \(n \geq N\) guarantees that it never happens that \(d_i = 0\) for all \(i\).

Counting

Let us subtract the count with \(n < N\) lastly, so we can ignore the first condition and assume that \(n\) is a non-negative integer. Since \(f(n) \leq N\) for \(n \leq N\), there are \(\lfloor \frac{n}{9} \rfloor\) such non-negative integers \(n\).

Considering the behavior of the greedy algorithm above to find \(f(n)\) , we see that, for \(Q\) and \(R\) when \(n\) is divided by \(10^{M-1}\), \(f(n) = Q + (\text{digit sum of }R)\) .

Therefore, the problem has been boiled down to the following:

Find the number, modulo \(998244353\), of tuples of non-negative integers \((A_0, A_1, \ldots, A_{M - 1})\) such that:

• \(0 \leq A_i \leq 9\) for \(i = 0, 1, \ldots, M - 2\) (note that \(A_{M - 1}\) is not constrained)
• \(S \leq N\) and \(S \equiv N \pmod 9\), where \(S = \sum A_i\).

Let \(f_n\) be the number of tuples of non-negative integers that satisfy the former condition, and \(f = \sum f_nx^n\). Then \(f = \frac{(1 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8 + x^9)^{M-1}}{1-x}\). The terms (up to degree \(N\)) of this Formal Power Series (FPS) can be computed in various ways. Dividing with \((1 - x)\) corresponds to taking the cumulative sums of the coefficients, so it suffices to compute \({(1 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8 + x^9)^{M-1}}\). This is a famous problem, and the following methods are known:

• Establish a differential equation, and incrementally obtain the coefficients utilizing the small exponents (Reference: Library Checker)
• Use log and exp of FPS to compute the power of FPS (Reference: Library checker)
• Use convolutions of FFT and fast exponentiation to compute the power of FPS

The computational complexities are \(O(N), O(N \log N)\), and \(O(N \log N \log M)\), in order, which are all fast enough to get AC (accepted) if the constant factor is sufficiently small.

There are many other solutions, such as using the formula for the sought value \([x^N] \frac{(1-x^{10})^{M-1}}{(1-x)^M(1-x^9)}\) which takes into account the second condition too.