解题思路

演变规则分析
设当前序列长度为 $L$ ，其中数字 $1$ 的个数为 $c_1$ ，数字 $0$ 的个数为 $c_0 = L - c_1$ 。
- 每个 0 变为 1，贡献长度 $1$ ；
- 每个 1 变为 01，贡献长度 $2$ 。
  一轮演变后，新序列长度 $L' = c_0 \times 1 + c_1 \times 2 = L + c_1$ 。
状态转移

题目内容

有一个初始序列，仅由数字 0 和 1 组成。在每一轮演变中，序列中的每个数字会按照以下规则同时进行变换，然后将所有变换结果按原顺序拼接形成新序列：

现在给定初始序列以及需要进行的演变轮数 $n$ ，请你求出经过 $n$ 轮演变后序列的长度。由于结果可能非常大，请输出长度对 $10^9+7$ 取模后的值。

本题包含多组测试数据。序列的长度不超过 $10^5$ ，轮数 $n$ 不超过 $10^{18}$ ，所有测试数据中 $n$ 的总和不超过 $3 \times 10^5$ 。