制約より条件を満たす数列 \(A\) の要素は相異なるので、条件を満たすソート後の列 \((b_1, b_2, \dots, b_N)\) の個数を数えて \(N!\) 倍して答えを求めることにします。

便宜上 \(b_0 = 0, b_{N+1} = M\) として、階差に注目すると次の事実がわかります。

• \(1 \leq i \leq N-1\) の範囲では \(b_{i+1} - b_i\) は正の奇数
• \(b_1 - b_0\) および \(b_{N+1} - b_N\) は非負整数

値に関する母関数を考えます。非負整数と正の奇数に対応する母関数は \(\frac{1}{1-x}\) と \(\frac{x}{1-x^2}\) ですから、

\[[x^M] \left(\frac{x}{1-x^2}\right)^{N-1} \frac{1}{(1-x)^2}\]

が答えということになります。変形すると

\[[x^{M-(N-1)}] \frac{1}{(1+x)^{N-1}} \times \frac{1}{(1-x)^{N+1}}\]

となるので、

\[\frac{1}{(1-x)^n} = \sum_{i=0}^\infty \binom{i+n-1}{n-1} x^i\]

の公式を使用すれば答えを計算できます。