$O(N^2S)$ の解法を紹介します。初めに、 $X=N^2$ とします。
ここで、以下のようなDPを考えます。
$dp[i][j] := $ $1$ 以上 $M$ 以下の整数から $i$ 種類の数字を選び、合計を $j$ にする場合の数
求めたいものは $dp[X][S]$ です。

ここで、 $dp[i][j]=dp[i][j-i]+dp[i-1][j-i]-dp[i-1][j-M-1]$ であることを示します。
$i$ 種類の数字を選び、合計が $j$ になるような数集合で $1$ を含まないものと含むものを考えます。 $1$ を含まないものについて、選んだ数は全て $2$ 以上なのでこれらから全て $1$ を引くことで $i$ 種類の数字を選び、合計が $j-i$ になるような数集合にすることができます。同様に $1$ を含むものについても全て $1$ を引き、このとき $0$ が ( $1$ を消したことで) 存在するのでこれを消すことで $i-1$ 種類の数字を選び、合計が $j-i$ になるような数集合にすることができます。

よって、これより $dp[i][j]=dp[i][j-1]+dp[i-1][j-i]$ としたいですが、これでは $i$ もしくは $i-1$ 種類の数字を選び、合計が $j-i$ になるような数集合で、 $M$ を含んでいるものに対して対応できません。このような数集合に対し、 ( $i-1$ 種類の整数があるものについて $0$ を足した後) 全ての要素に $1$ を足し、 $M+1$ を引くことで $i-1$ 種類の数字を選び、合計が $j-M-i$ になるような数集合にすることができます。

以上より上の漸化式が正しいことが示され、この問題は \(O(XS)\) すなわち \(O(N^2S)\) で解くことができました。