答えが \(K\) 以下になるケースの個数を数えます。判定問題は貪欲に取り続けていけばよく、始めあまりが \(v = 0\) の状態から初めて、\(v\) を \(\max(v+A_i-K,0)\) に置き換えていき常に \(v\) が \(K\) 以下であれば可能、そうでないならば不可能となります。

\(v\) の遷移の列を \((v_0,v_1,\dots,v_N)\) と置きます。(\(v_0 = 0\) とします。) この \(v\) に対応する列の特徴を考えます。主に以下の \(3\) 種類に分けられます。

• $v_i,v_{i+1} = 0$ の場合
$X_i$ は $0$ 以上 $K$ 以下の任意の値を取れます。
• $v_l=v_r=0,v_{l+1},v_{l+2},\dots,v_{r-1}$ は $1$ 以上の場合
$X_l,X_{l+1},\dots,X_{r-2}$ は全て $K$ となり、$X_{r-1}$ が $0$ 以上 $K-v_{r-1}$ 以下の任意の値を取れます。
• $v_l=0,v_{l+1},v_{l+2},\dots,v_{N}$ は $1$ 以上の場合
$X_l,X_{l+1},\dots,X_{N-1}$ は全て $K$ となり、$X_{N}$ が $K-v_{r-1}$ になります。

\(x\) を \(X\) の総和、\(y\) を列の長さとした母関数を考えるとそれぞれ

\[ y(1+x+...+x^K) = \frac{y(1-x^{K+1})}{1-x}\]

\[ \left(\sum_{i \ge 2} y^iK^{i-2}x^{(i-1)K} \right) (Kx + (K-1)x^2 + ... + x^K) = \frac{y^2x^K(x-(K+1)x^{K+1}+Kx^{K+2})}{(1-Kyx^K)(1-x)^2}\]

\[ \left(\sum_{i \ge 1} y^iK^{i-1}x^{iK} \right) (x + x^2 + ... + x^K) = \frac{yx^K(x-x^{K+1})}{(1-Kyx^K)(1-x)}\]

となります。ただし、最後のパターンは \(1\) 回しか使えません。よって、答えが \(K\) 以下になるケースの個数は

\[ \displaystyle [x^M y^N] \frac{1 + \frac{yx^K(x-x^{K+1})}{(1-Kyx^K)(1-x)}}{1 - \left(\frac{y(1-x^{K+1})}{1-x}\right)-\left(\frac{y^2x^K(x-(K+1)x^{K+1}+Kx^{K+2})}{(1-Kyx^K)(1-x)^2}\right)} \]

となります。ところで、この式は \(x,x^K,k,\frac{y}{1-x}\) による低次数な式で書き示すことが出来ます。非常に長くなりますが書き記すと、

\[ \displaystyle [x^M y^N] \frac{1-Kx^K(1-x)\frac{y}{1-x} +x^K(x-x^{K+1}) \frac{y}{(1-x)}}{1-Kx^K(1-x)\frac{y}{1-x} - (1-x^{K+1})\left(1-Kx^K(1-x)\frac{y}{1-x}\right)\frac{y}{1-x} - x^K(x-(K+1)x^{K+1}+Kx^{K+2}) \left(\frac{y}{1-x}\right)^2} \]

となります。\(x,x^K,k,\frac{y}{1-x}\) を \(p,q,r,s\) と置いて上式を展開した時の \(p^aq^br^cs^d\) の係数を \(f_{a,b,c,d}\) と置きます。ここで、分母に含まれる項は全て \(s\) を含むことから \(a,c \le d,b \le d+1\) である部分以外係数は \(0\) となります。これを踏まえると、\(f_{a,b,c}\) を \(f_{a,b,c,N}\) で置き換えると

\[ [x^M] \sum_{K \ge 0} \sum_{a,b,c} \frac{f_{a,b,c}x^a x^{Kb} K^c}{(1-x)^N} \]

を求める問題に帰着されます。\(f_{0,0,0} = 1\) ですが、今求めている値は答えが \(K\) 以下になるケースの個数の総和で、本来求めるべきものは答えが \(K\) 以上になるケースの個数の総和であることを考慮すると結局 \(f_{0,0,0}\) が打ち消されるため問題ありません。この時点で \(b \ge 1\) になることに注意して下さい。ここで、\(a,b,c\) を固定してみると式は

\[ \frac{f_{a,b,c} x^a}{(1-x)^N} \sum_{K \le 0} x^{Kb} K^c \]

となりますが、sigma 部分はある \(c\) 次多項式 \(P(x)\) によって \(\displaystyle \frac{P(x^b)}{(1-x^b)^{c+1}}\) と表されます。つまり、\(b\) を固定した際の

\[\sum_{K \ge 0} \sum_{a,c} \frac{f_{a,b,c}x^a x^{Kb} K^c}{(1-x)^N} \]

は \(\displaystyle \frac{Q(x)}{(1-x)^N(1-x^b)^{N+1}}\) という表示を持ちます。ということは、当然 \(\displaystyle \frac{R(x)}{(1-x^b)^{2N+1}}\) という表示も持ちます。なので \(d = M \bmod b\) とすると、\([x^{d+bk}] \displaystyle \frac{R(x)}{(1-x^b)^{2N+1}}(k = 0,1,2,...)\) はある \(2N\) 次の多項式 \(g(x)\) によって \(g(k)\) と表されるということです。

あとは \(k \le 2N\) の範囲で係数列を求めればよいですが、\(a,c\) は \(N\) 以下、\(K\) は \(2N\) 以下を考えればよいため \(1\) 個の \(b\) について \(\mathrm{O}(N^3)\) で係数列を求め、多項式補間を \(\mathrm{O}(N^2)\) かけると全体で \(\mathrm{O}(N^4)\) でこの問題を解くことが出来ます。