T524402 IMAWANOKIWA (Counting ver.)

数据太大了没放，有需要的可以私信。 [IMAWANOKIWA - いよわ / 初音ミク](https://www.bilibili.com/video/BV1iE411Y7bf) > あなたの未来が見たかった。

> 给你一个初始长度为 $n$，**只包含** $\mathbf{0, 1, 2}$ 的序列 $a_{1 \sim n}$，你可以执行以下操作： > > - 选择一个位置 $j$（$1 \le j < |a|$），删去 $a_j, a_{j + 1}$，并在原位置插入 $\mathrm{popc}(a_j + a_{j + 1})$。其中，$\mathrm{popc}(x)$ 表示 $x$ 在二进制表示下 $1$ 的个数。 > > 显然每次操作后序列长度都会减少 $1$，所以执行 $n - 1$ 次操作后，这个序列会恰好剩下一个数。 > > 请你求出剩下的这个数可能的最小值，并给出一个对应的操作序列。 > > 定义操作序列 $p_{1 \sim n - 1}$ 为一个长度为 $n - 1$ 的正整数序列，其中 $p_i$ 表示第 $i$ 次操作所选择的 $j$（显然 $1 \le p_i \le n - i$）。你需要满足按照这个操作序列操作得出的最后一个数最小。 > > 如果有多种对应的操作序列，请你给出字典序最小的操作序列。 上面是 [IMAWANOKIWA (Construction ver.)](https://www.luogu.com.cn/problem/P11269) 的题面，但是你需要解决另外一个相关的问题： 给你 $n$ 与一个长度为 $n - 1$ 的操作序列 $b_{1 \sim n - 1}$，你需要求出有多少个长度为 $n$，**只包含** $\mathbf{0, 1, 2}$ 的序列 $a_{1 \sim n}$ 满足它的最小字典序操作序列为 $b$。 由于问题的答案可能很大，请你将其对 $10^9 + 7$ 取模。

无

无

**【样例解释】** 对于第一组数据，合法的序列 $a$ 有以下八种： $$ [0, 1, 0, 1, 2, 1]\\ [0, 2, 0, 1, 2, 1]\\ [1, 0, 0, 1, 2, 1]\\ [1, 1, 0, 1, 2, 1]\\ [1, 2, 0, 2, 2, 2]\\ [2, 0, 0 ,1, 2, 1]\\ [2, 1, 0, 2, 2, 2]\\ [2, 2, 0, 1, 2, 1]\\ $$ **【数据范围】** **本题使用捆绑测试与子任务依赖。** 设 $\sum n$ 为单个测试点内所有的 $n$ 之和。 对于 $100\%$ 的数据，$2 \le n, \sum n \le 2 \times 10^6, 1 \le b_i \le n - i$。 | 子任务编号 | $\sum n$ | 特殊性质 | 分数 | 子任务依赖 | | :-: | :-: | :-: | :-: | :-: | | $1$ | $\le 10$ | 无 | $10$ | 无 | | $2$ | $\le 15$ | 无 | $10$ | $1$ | | $3$ | $\le 300$ | 无 | $20$ | $1, 2$ | | $4$ | $\le 3 \times 10^3$ | 无 | $20$ | $1, 2, 3$ | | $5$ | $\le 10^5$ | A | $20$ | 无 | | $6$ | $\le 2 \times 10^6$ | 无 | $20$ | $1, 2, 3, 4, 5$ | 特殊性质 A：保证 $b$ 序列中全为 $1$。