解题思路
本题的目标是计算长度为 n 的二进制序列中，不存在连续 k 个 1 的序列个数，并对 109+7 取模。数据范围中 k 可以很大，但 n 只有 103，且所有测试数据的 n 之和不超过 103。
核心观察：若 k−1≥n，则任意序列中连续 1 的个数最多为 n，必然小于 k，此时所有 2n 个序列均合法，直接输出 2nmod(109+7)。
动态规划
定义 dp[i] 表示长度为 i 的合法密码数量。考虑如何从前面的状态转移：
题目内容
在一款高安全电子锁中，密码是一个长度为 n 的二进制序列（只包含 0 和 1）。系统有一条保护规则：如果密码中存在连续 k 个 1，就会触发警报并锁定设备。因此，有效的密码必须满足：序列中任意一段连续 1 的个数都严格小于 k。
给定整数 n 和 k，请你计算有多少个长度为 n 的二进制序列符合上述要求。由于答案可能很大，请输出其对 109+7 取模的结果。
数据范围：测试数据组数 T 不超过 103，每组中的 n 不超过 103，k 不超过 109，且所有测试数据的 n 之和不超过 103。
输入描述
