首先题解中给出结论：

最后一个条件不成立，当且仅当能将 $S_1,S_2,\cdots,S_m$ 划分为两组 $L,R$，使得 $\displaystyle\max_{a\in S,S\in L}a<\min_{a\in S,S\in R}a$ 。

证明题解中有，就略去了。

在此基础上，考虑容斥，设 $f_{n,m}$ 为答案，$g_{n,m}=\displaystyle{ n\brace m}$，则

$$g_{n,m}\sum_k\sum_{\small\sum_{i=1}^ka_i=n\atop\sum_{i=1}^nb_i=m}f_{i,j}$$

即，将 $1,2,\cdots,n$ 任意划分为 $m$ 个无标号非空集合，等价于将 $m$ 个集合划分为 $k$ 组 $T_1,T_2,\cdots,T_k$，使得 $\forall i\in[1,k),\displaystyle\max_{a\in S,S\in T_i}a<\min_{a\in S,S\in T_{i+1}}a$ 。

显然该式可用二元生成函数表示

$$g(x,y)=\dfrac{1}{1-f(x,y)}$$

$$f(x,y)=1-\dfrac{1}{g(x,y)}$$

$\Theta(nm)$ 预处理出第二类斯特林数后，$\Theta(n^2\log n)$ 二维 FFT + 多项式求逆即可。

因为要任意模数 NTT，所以跑的还没 $\Theta(n^3)$ 快，希望出题人下次给个 NTT 模数。。。