箱 \(0\) にボールを \(k\) 個入れるような方法の個数は \(\binom{N}{k} m^{N-k}\) 通りあります。これの総和を取った \(\sum_{k=0}^{K} \binom{N}{k} m^{N-k}\) を \(m =0,1,\dots,M\) に対して求めればよいです。

\(f(x) = \sum_{k=0}^{K} \binom{N}{k} x^{N-k}\) とすると、求めるべき値は \(f(0),f(1),\dots,f(M)\) となります。このように多項式の値を複数の点について評価するような問題は、Multipoint Evaluation というアルゴリズムを用いて解くことが出来ます。

簡単に説明すると、\(f(a) = f(x) \bmod (x-a)\) であることを利用して \(f(x) \bmod (x-a_1)(x-a_2)...(x-a_k)\) を分割統治で計算していくアルゴリズムです。詳しい解説は https://37zigen.com/multipoint-evaluation/ などをお読みください。

このアルゴリズムを適用することで \(\mathrm{O}(N\log N + M \log^2 M)\) で解けます。