思路

• 设 $L=r-1$。若 $L \ge n$，限制无效，答案为 $2^n \bmod M$（其中 $M=10^9+7$）。

• 令 $f[i]$ 为长度为 $i$ 的合法串数量。

  • 初值：对 $0 \le i \le L$，有 $f[i]=2^i$。

  • 递推：当 $i \ge L+1$（即 $i \ge r$），

    $$f[i] = \sum_{t=1}^{r} f[i-t]$$

题目内容

【引用开始】

在若干链路层协议中(如 HDLC)，帧边界由标志字段确定。为便于理论分析，约定标志字段为一段“连续的， $r$ 个 $1$ ”(即形如 $11...1$，长度为 $r$ )。本题仅关注载荷部分：载荷按位发送，且不进行任何比特填充、字节对齐、$CRC$ 校验或转义。为了避免载荷误触发“伪旗标”，需要保证载荷内部不出现“连续的 $r$ 个 $1$ "

注意：帧的起止标志不计入载荷长度；不考虑跨帧拼接，也不考虑接收端的粘包现象。比特流按从高位到低位发送或从低位到高位发送均不影响计数结果。

​ 【引用结束】

给定整数 $n$ 和 $r$ 。一帧数据内容由一个长度恰为 $n$ 的二进制串构成(不含首尾标志)。标志定义为“连续 $r$ 个 $1$ "。统计有多少个长度为 $n$ 的二进制串，其任意连续的 $1$ 的长度严格小于(等价地，最大连续 $1$ 的长度至多为 $L=r-1$ )。

请将答案对 $10^9 +7$ 取模后输出。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T(1≦T≦10^3)$ ，表示测试组数。

接下来 $T$ 行，每行输入两个整数 $n,r(1≦n≦10^3;1≦r≦10^9)$ 。

除此之外，保证单个测试文件的 $\sum n ≦10^3$ 。

输出描述

输出 $T$ 行，每行一个整数，表示长度为 $n$ 的二进制串中，最大连续 $1$ 的长度严格小于 $r$ 的方案数(对 $10^9 +7$ 取模)。

样例1

输入

3
5 3
7 10
8 2

输出

24
128
55