时间限制： 1.0 秒

空间限制： 512 MB

题目背景

所谓 Fib-AVL 树，就是每一个非叶子节点的右子树高度都比左子树高度大 1 的二叉树。例如下图中为高度 $h=1,2,3$ 的 Fib-AVL 树。在本题中，根节点的深度定义为 $0$。

题目描述

设高度为 $h$ 的 Fib-AVL 的节点总数为 $\eta(h)$。你需要对给定的 $h$ 求出对应的 $\eta(h)$。

由于答案可能很大，你只需要给出答案对 $10^9+7$ 取模的值即可。

输入格式

从标准输入读入数据。

输入只有一行，为正整数 $h$。

输出格式

输出到标准输出。

输出一行一个整数，为 $\eta(h)$ 对 $10^9+7$ 取模的值。

1

2

2

4

3

7

子任务

对于所有数据，保证 $1\le h\le 10^5$。

本题无数据梯度，需要通过全部数据获得所有分数。

来源

清华 826 考研初试 2026 - 算法大题（1）