称序列 $⟨a_1,\cdots ,a_n⟩$ 是避免 120 的，当且仅当不存在 $1\le k<j<i\le n$，满足 $a_i<a_k<a_j$。

假设 $a_1,\cdots ,a_{i-1}$ 已经确定了，现在要确定 $a_i$。那么为使 $a$ 避免 120，只需满足 $a_i\ge \underset{k<j<i,a_k<a_j}{\max }{a}_k$ 即可，将满足 $k<j\wedge a_k<a_j$ 的记作 $(k,j)$ 组合。

设 $h_{n,X}$ 表示长度为 $n$ 的非负整数序列 $⟨a_1,\cdots ,a_n⟩$ 的个数，满足：

1. $a_1\ge 1$。
2. $a$ 是避免 120 的。
3. 设 $A_i$ 表示满足 $1\le j\le i$ 且 $a_{j-1}<a_j$ 的 $j$ 的个数（将 $a_0$ 看作一个负数），那么 $a_i\le X+A_{i-1}+1$。

那么原题目的答案等于 $\sum _{i=m}^N{h}_{N-m,0}$，其中 $m$ 枚举的是从 $a_1$ 开始的极长的一段连续的 $0$：$a_1,\cdots ,a_m$。

考虑怎么求 $h_{n,X}$。先枚举 $a_1\in [1,X+1]$，再枚举从 $a_1$ 开始的极长的一段小于等于 $a_1$ 的数：$a_1,\cdots ,a_m$。

注意到 $(1,m+1)$ 这个组合给 $i>m+1$ 的 $a_i$ 带来 $\ge a_1$ 的限制。进一步地，可以发现对于 $j\le m$ 的 $(j,k)$ 组合，它们对 $i>m+1$ 的 $a_i$ 的限制恰是 $\ge a_1$。

这相当于 $a_{m+1},\cdots ,a_n$ 集体减去 $a_1$ 后都非负，但注意 $a_{m+1}$ 还需是正的。

然后还要枚举 $⟨a_1,\cdots ,a_m⟩$ 中的上升连续对的个数 $t$，以确定 $A_m$。

那么容易得到：
$$h_{n,X}=\sum _{a_1=1}^{X+1}\sum _{m=1}^n\sum _{t=1}^m{g}_{m,a_1,t}\cdot h_{n-m,X+t-a_1}$$

其中：

设 $g_{n,x,t}$ 表示长度为 $n$ 的非负整数数列 $⟨a_1,\cdots ,a_n⟩$ 的个数，满足：

1. $a_1=x$，且对于任意 $1<i\le n$ 有 $a_i\le a_1$。
2. $a$ 是避免 120 的。
3. 恰好存在 $t$ 个位置 $i$（$1\le i\le n$，将 $a_0$ 看作一个负数），使得 $a_{i-1}<a_i$。

考虑怎么求 $g_{n,x,t}$。考虑枚举 $a_2=y$。

若 $y=x$，那么直接从 $g_{n-1,x,t}$ 转移过来即可；

若 $y<x$。同样地枚举从 $a_2=y$ 开始的极长的一段小于等于 $a_2$ 的数 $a_2,\cdots ,a_m$。类似地，对于 $j\le m$ 的 $(j,k)$ 组合，它们对 $i>m+1$ 的限制恰是 $\ge y$。

从而有：
$$g_{n,x,t}=g_{n-1,x,t}+\sum _{y=0}^{x-1}\sum _{m=1}^{n-1}\sum _{c=1}^m{g}_{m,y,c}\cdot f_{n-m-1,x-y,t-c}$$
其中：

设 $f_{n,L,t}$ 表示长度为 $n$、值域在 $[0,L]$ 的整数数列 $⟨a_1,\cdots ,a_n⟩$ 的个数，满足：

1. $a_1>0$。
2. $a$ 是避免 120 的。
3. 恰好存在 $t$ 个位置 $i$（$1\le i\le n$，将 $a_0$ 看作一个负数），使得 $a_{i-1}<a_i$。

考虑怎么求 $f_{n,L,t}$。先枚举 $a_1\in [1,L]$。类似地枚举极长的一段小于等于 $a_1$ 的数 $a_1,\cdots ,a_m$。类似地，对于 $j\le m$ 的 $(j,k)$ 组合，它们对 $i>m+1$ 的限制恰是 $\ge a_1$。

那么：
$$f_{n,L,t}=\sum _{a_1=1}^L\sum _{m=1}^n\sum _{c=1}^m{g}_{m,a_1,c}\cdot f_{n-m,L-a_1,t-c}$$

下图可能可以帮助你更好地理解上述过程：

现在，我们已经可以在 $O(N^6)$ 的时间复杂度内解决原问题。一个常数优化的小技巧是，注意到 $h,g,f$ 最后一维记录上升连续对的个数，而这个个数其实在严格的限制下并不多，大概只有序列长度的一半，这样可以省掉很多常数。

事实上，可以注意到所有转移方程都是卷积的形式。我们先考虑用生成函数来表示 $f$ 和 $g$。

先把 $g$ 的转移方程改写如下：
$$\begin{array}{rl}{g}_{n,x,t}& =g_{n-1,x,t}+\sum _{y=0}^{x-1}\sum _{m=1}^{n-1}\sum _{c=1}^m{g}_{m,y,c}\cdot f_{n-m-1,x-y,t-c}\\ & =\sum _{y=0}^x\sum _{m=1}^{n-1}\sum _{c=1}^m{g}_{m,y,c}\cdot f_{n-m-1,x-y,t-c}\end{array}$$
这方便于我们列方程。

设 $F(x,y,z)$ 和 $G(x,y,z)$ 分别为 $f,g$ 的生成函数。那么有：

$$\{\begin{array}{l}G=xGF+\frac{xz}{1-y}\\ F=F(G-\frac{xz}{1-x})+\frac{1}{1-y}\end{array}$$

可能可以半在线卷积。或者可以直接解得：
$$G=\frac{1-y-\sqrt{4(1-x)x(1-y)(x(1-z)-1)+(1-y-x(x-y)(1-z){)}^2}+x^2(1-z)-x(2-y)(1-z)}{2(1-x)(1-y)}$$
使用三元 GF 应该可以做到 $O(n^3\mathrm{polylog}(n))$。

求 $H$ 应该也能用类似半在线卷积的方法加速至 $O(n^3\mathrm{polylog}(n))$？