幇助原理を使わない解答を紹介します。 $X=M-N$ とし $ans[i]$ を以下のように定めます。

答えは $ans[N] \times M \times (M-1) \times \cdots \times (M-N+1)$ です。
そこで、 $ans[N]$ を求めることを考えます。

初めに、 $ans[1]=X,ans[2]=X^2+X+1$ です。 $ans[1]$ は $B$ としてありえるのが $(2),(3), \cdots , (X+1)$ であることより分かります。 $ans[2]$ は $B$ としてありえるのが $B_1=2$ のとき $X+1$ 通り、 $B_1 \neq 2$ のとき $X$ 通りであることより分かります。

$i \geq 3$ について $ans[i]$ を考えます。
$B_i \geq i+1$ のとき、 $B_1$ から $B_{i-1}$ としてありえる通り数は $ans[i-1]$ 通りです。
$B_i \leq i-1$ のときを考えます。ここでは、 $B_i = 1$ とします。 $B_1=i$ とする場合、 $B_2$ から $B_{i-1}$ としてありえる通り数は $ans[i-2]$ 通りです。
また、 $B_1 \neq i$ とする場合、 $B_1$ から $B_{i-1}$ としてありえる通り数は $ans[i-1]$ 通りです。これは $i$ を $1$ としてみなしても問題がないことより分かります。
同様の議論より、 $1 \leq j \leq i-1$ について $B_i=j$ となる $B$ は $ans[i-1]+ans[i-2]$ 通りあることが分かります。

これらより、 \(ans[i]=(X+i-1)\times ans[i-1] + (i-1) \times ans[i-2]\) が示され、これに沿って \(ans[N]\) を \(O(N)\) で求めることができます。