\(O(N^3)\) で解くことができます。 公式解説の分解を用います。 つまり、 \([N]\) の分割 \(A, B\) であって、\((a, b) \in A \times B\) はすべて、\(a \rightarrow b\) と向きつけられているようなものを数える方針です。

\(|A| = L\) を固定したときの \(x \rightarrow y (x < y)\) の数の母関数を考えます。この辺を以降「良い辺」と呼びます。

\(A, B\) 内の向きつけは自由なので、\((1 + x) ^ {L(L-1)/2 + (N-L)(N-L-1)/2}\) です。

一方で、A, B を合体させる際は要素の順番の大きさに気を配る必要があります。 AB 間の良い辺の数は、\(L\) 個の 1, \(N-L\) 個の 0 を並べた配列の転倒数に対応するので、これは \(q\)-二項係数 \(\binom{N}{L}_q\) であらわすことができます。

よって、

\([q^M] \sum_{L=0}^{N-1} (1+q)^{L(L-1)/2+(N-L)(N-L-1)/2} \binom{N}{L}_q\)

が求める答えです。 ところで、\(q\)-binomial の表式は

\(\binom{N}{L}_q = \dfrac{(1-q)(1-q^2)\ldots(1-q^N)}{(1-q)\ldots(1-q^L) (1-q) \ldots (1-q^{N-L})}\)

であったので、 \(\binom{N}{L + 1}_q = \binom{N}{L}_q \dfrac{1-q^{N-L}}{1-q^{L+1}}\)

の等式が成り立つ。

よって、\(\binom{N}{i}_q\) の列挙は全体で \(O(N^3)\) ですることができる。 これにより、

\([q^M] \sum_{L=0}^{N-1} (1+q)^{L(L-1)/2+(N-L)(N-L-1)/2} \binom{N}{L}_q\)

\(= \sum_{L=0}^{N-1} \sum_{i=0}^{L(N-L)} [q^i] \binom{N}{L}_q \binom{L(L-1)/2 + (N-L)(N-L-1)/2}{M-i}\)

と求めることができる。

実装: (https://atcoder.jp/contests/arc163/submissions/59329813)

\(N = 1000\) でも 2 秒以内に求解できます。