公式解説とは少し異なりますが、 kyopro_friends さんの解説と同様に「各要素が \(M+1\) 種類のいずれかで、そのうち指定された \(m\) 個の要素のみがちょうど奇数回現れる長さ \(n\) の array」の個数を求めることを考えます。これは、

\[\cosh x =\frac{e^x+e^{-x}}{2}=1+\frac{x^2}{2!}+\frac{x^4}{4!}+\dots \]

\[\sinh x =\frac{e^x-e^{-x}}{2}=x+\frac{x^3}{3!}+\frac{x^5}{5!}+\dots \]

としたとき、\((\sinh x)^m(\cosh x)^{M+1-m}\) の \(x^n\) の係数に \(n!\) をかけたものと等しいです。よって、fps の pow を用いることで、すべての \(n,m\) に対する答えを \(O(N^2\log N)\) で求めることができます。想定解より計算量は悪化しますが、ボトルネックである桁 DP の計算量 \(O(N^3\log M)\) より軽いため十分間に合います。FPS を用いることに慣れている & ライブラリを整備している人にとっては、ほとんど考察も実装もいらないため「計算量は悪化するが楽な解法」と言えるでしょう。

なお、\(f_m(x)=(\sinh x)^m(\cosh x)^{M+1-m}\) の両辺を微分すると \(f_m'(x),f_{m-1}(x),f_{m+1}(x)\) の関係式が得られるため、係数比較によって公式解説と同じ DP を得ることも可能です（maspy さんの提出を参考にさせて頂きました）。