时间限制： 1.0 秒

空间限制： 20 MB

题目背景

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

题目描述

请设计一个算法，在高度为 $h$ 的 Fib-AVL 树中，对于任意的 $0\le k\le h$，计算深度为 $k$ 的节点总个数 $s(h,k)$，要求时间复杂度为 $O(h)$，空间复杂度为 $O(h)$。

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

输入格式

从标准输入读入数据。

输入一行两个整数 $h,k$。

输出格式

输出到标准输出。

输出一行一个整数，表示高度为 $h$ 的 fib-AVL 树中，深度为 $k$ 的节点个数对 $10^9+7$ 取模的值。

114514 1919

775276710

子任务

对于所有数据，保证 $1\le h\le 10^6,~0\le k\le h$。

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

提示

请注意本题非同寻常的空间限制，如有需要，请使用 int 类型的静态数组进行存储。此外，引用万能头（bits/stdc++.h）或者使用动态数组 vector 也会消耗大量空间，建议不要使用。

此外，由于本题每个测试点拥有多组数据，建议在重复的一个全局静态数组上进行计算，注意多组数据的情况下，数组需要初始化。

请注意加强版和普通版在数据范围以及时间复杂度要求上的区别，将时间复杂度优化到 $O(h)$ 还是需要一些数学功底的哦~

再额外给一个提示，可以在互联网上查询“逆元”的概念，并实现一个 $O(h)$ 时间和空间复杂度预处理，$O(1)$ 求组合数对足够大的质数取模的做法，这会为你完成本题起到关键作用。

来源

清华 826 考研初试 2026 - 算法大题（2）（数据范围有所加强）