If \(M \bmod K \neq 0\), the answer is \(0\). From now on, let’s set \(M := \frac{M}{K}\).

Let’s call the operation of reducing \(A_i\) by \(K\) as operation \(1\), and the operation of reducing each of \(A_i, A_{i+1}, \dots, A_{i+K-1}\) by \(1\) as operation \(2\).

Applying operation \(2\) \(K\) times to a certain \(i\) is equivalent to applying operation \(1\) once to each of \(i, i+1, \dots, i+K-1\). Therefore, we may assume that the number of times operation \(2\) is applied to each \(i\) is less than \(K\). Let’s assume this from here on.

\(A_1 \bmod K\) is not reduced by operation \(1\), so it needs to be made \(0\) by operation \(2\). Hence, operation \(2\) will be performed \(A_1 \bmod K\) times for \(i=1\). Similar reasoning can be applied to \(A_2, A_3, \dots, A_{N-K+1}\), so the number of times operation \(i\) is performed for \(i=2, 3, \dots, N-K+1\) is uniquely determined.

Here, let’s fix the sequence \(B=(B_1, B_2, \dots, B_{N-K+1})\), where \(B_i\) is the number of times operation \(2\) is performed for \(i\), and count the number of \(A\)’s that can achieve the goal and realize this \(B\). Since the number of times operation \(2\) is performed is fixed, we must use operation \(1\) to satisfy the condition on the sum.

If we express the answer using formal power series, it is \([x^M]\frac{x^{\sum B}}{(1-x)^N}\). If you take the sum for all \(B\), it becomes \([x^{M}]\left(\frac{1-x^K}{1-x}\right) ^{N-K+1} \times \frac{1}{(1-x)^N}\).

After rearranging the above, the problem becomes finding \([x^M] \left(\frac{(1-x^K)^{N-K+1}}{(1-x)^{2N-K+1}}\right)\). Expanding the numerator with the binomial theorem, we need to find \([x^{M-iK}] \frac{1}{(1-x)^{2N-K+1}}\) for \(i=0, 1, \dots, N-K+1\). This is equal to \(\binom{M+2N-(i+1)K}{2N-K}\) from the negative binomial theorem.

Even if you calculate this binomial coefficient naively, it takes \(\mathrm{O}(N)\) time, so the enumeration for \(i=0, 1, \dots, N-K+1\) is possible in \(\mathrm{O}(N^2)\). Therefore, the problem is solved in \(\mathrm{O}(N^2)\), which is sufficiently fast.