原案者です。形式的冪級数を用いて DP の遷移を高速化し、\(O(N^2 \log^2 N)\) で解く方法を示します。DP の定義や更新方法については公式解説をご参照ください。

なお、本問題は埋め込みを防ぐために任意 mod にしているため、畳み込みの定数倍が重く、実際に \(O(N^3)\) 解法より高速に動作するかは未検証です。

配る DP で考えます。\(\mathrm{dp}_{i,*}\) からの遷移先が全て同じであることを利用して、これらの遷移を同時に行います。遷移を具体的に式で表すと、各 \(1 \leq k < N-i\) に対して

\[\mathrm{dp}_{i+k,k} \leftarrow \mathrm{dp}_{i+k,k} + 2^{k(k-1)/2}\binom{N-i-1}{k}\sum_{j=1}^{i} (2^j-1)^k\mathrm{dp}_{i,j}\]

であるため、形式的冪級数 \(f\) を

\[f=\sum_{j=1}^{i} \frac{\mathrm{dp}_{i,j}}{1-(2^j-1)x}\]

とおけば、

\[\mathrm{dp}_{i+k,k} \leftarrow \mathrm{dp}_{i+k,k} + 2^{k(k-1)/2}\binom{N-i-1}{k}[x^k]f\]

と表せるので、\(f\) の \(x^1,x^2,\ldots, x^{N-i-1}\) の係数が高速に求められれば良いです。実際、\(f\) を通分して(総和記号を含まない)有理式として表したものが分割統治によって \(O(N \log^2N)\) で求まるため、\(\mathrm{dp}_{i,*}\) からの遷移をまとめて \(O(N \log^2N)\) で行えます。

よって、本問題を\(O(N^2 \log^2N)\) で解くことができました。