dp[\(i\)][\(j\)] := \(1\) 以上の整数 \(i\) 個で和が \(j\) になるような場合の数，ただし同じ整数を \(M\) 個以下しか使ってはならない とします．

\(1\) の個数で場合分けします．\(1\) が \(k\) 個 (\(0 \leq k \leq M\)) あるとき，\(2\) 以上を \(1\) ずつひいて場合の数はdp[\(i-k\)][\(j-i\)] です．\(i-k\) の範囲は連続しているので，累積和を計算しつつ更新していくと \(\mathrm{O}(NM)\) で答えが求まります．