動的計画法で解きます。

\(\mathrm{dp}[i][j]\) を、\(A\) の先頭から \(i\) 項を決めて、\(i\) 項目が \(j\) であるような場合の数とします。 この \(\mathrm{dp}\) の遷移は

\(\mathrm{dp}[i + 1][j] = (\mathrm{dp}[i][1]+\ldots + \mathrm{dp}[i][j - K])+(\mathrm{dp}[i][j + K]+\ldots + \mathrm{dp}[i][M])\)

です。（なお、\(1 > j - K\) のときや\(j + K>M\) のとき、\(K=0\) のときは微妙に遷移が異なるので注意してください。）この \(\mathrm{dp}\) では状態数が \(\mathrm{Ο}(NM)\) 、遷移が \(\mathrm{Ο}(M)\) となり、全体の計算量は \(\mathrm{Ο}(NM^2)\) となり実行時間制限に間に合いません。

ここで、\(\mathrm{dp}[i + 1]\) への遷移を考える際に事前に \(\mathrm{dp}[i]\) の累積和を求めておくことで、遷移が \(\mathrm{Ο}(1)\) で可能になり、全体の計算量が \(\mathrm{Ο}(NM)\) になります。これは十分高速です。