議論の都合上、数列\(X\)の順序を反転したものを考えることにします。 この時、良い数列\(X=(X_1,X_2,...,X_n)\)のスコアは \(X_i-X_{i+1}=1\)となる全ての\(i\)に対して\(X_i\)をかけたものになります。

\(a_{i,j}\)を長さが\(i\)、初項が\(B\)で末項が\(j\)の良い数列全てに対するスコアの総和とし、

\[f_i(x) = \sum_{j=0}^{\infty}a_{i,j}x^j\]

とします。

この時

\[ \left\{ \begin{array}{ll} f_1(x) = x^B \\ f_{i+1}(x) = xf_i(x)+\frac{d}{dx}f_i(x) &(i \geq 1) \end{array} \right. \]

が成り立ちます。

(下の式の右辺について、1項目は\(X_{i+1}=X_i+1\)、2項目は\(X_{i+1}=X_i-1\)となるものにそれぞれ対応します。)

ここで\(g_i(x) = f_i(x)e^{\frac{x^2}{2}}\)とおくと、

\[g_1(x)=x^Be^{\frac{x^2}{2}}\]

かつ

\[ \begin{array}{ll} \frac{d}{dx}g_i(x) &= \frac{d}{dx}(f_i(x)e^{\frac{x^2}{2}}) \\ &= (\frac{d}{dx}f_i(x))e^{\frac{x^2}{2}}+f_i(x)(xe^\frac{x^2}{2}) \\ &= (\frac{d}{dx}f_i(x)+xf_i(x))e^{\frac{x^2}{2}} \\ &= f_{i+1}(x)e^{\frac{x^2}{2}} \\ &= g_{i+1}(x) \end{array} \]

が成り立つので、

\[ g_i(x)=\left(\frac{d}{dx}\right)^{i-1} \left( x^Be^{\frac{x^2}{2}} \right) \]

です。したがって

\[ f_i(x) =e^{-\frac{x^2}{2}} \left(\frac{d}{dx}\right)^{i-1} \left( x^Be^{\frac{x^2}{2}} \right) \]

となり、求める答えは

\[ a_{N,A} = [x^{A}] \left(e^{-\frac{x^2}{2}} \left(\frac{d}{dx}\right)^{N-1} \left( x^Be^{\frac{x^2}{2}} \right) \right) \]

となります。 これは階乗とその逆元、2の逆元の累乗を前計算しておくと\(O(\max(N,A,B))\)時間で計算可能です。