P3615.第1题-载荷按位发送
题目内容
【引用开始】
在若干链路层协议中(如 HDLC)，帧边界由标志字段确定。为便于理论分析，约定标志字段为一段“连续的， r 个 1 ”(即形如 11...1，长度为 r )。本题仅关注载荷部分：载荷按位发送，且不进行任何比特填充、字节对齐、CRC 校验或转义。为了避免载荷误触发“伪旗标”，需要保证载荷内部不出现“连续的 r 个 1 "
注意：帧的起止标志不计入载荷长度；不考虑跨帧拼接，也不考虑接收端的粘包现象。比特流按从高位到低位发送或从低位到高位发送均不影响计数结果。
【引用结束】
给定整数 n 和 r 。一帧数据内容由一个长度恰为 n 的二进制串构成(不含首尾标志)。标志定义为“连续 r 个 1 "。统计有多少个长度为 n 的二进制串，其任意连续的 1 的长度严格小于(等价地，最大连续 1 的长度至多为 L=r−1 )。
请将答案对 109+7 取模后输出。
输入描述
每个测试文件均包含多组测试数据。第一行输入一个整数 T(1≦T≦103) ，表示测试组数。
接下来 T 行，每行输入两个整数 n,r(1≦n≦103;1≦r≦109) 。
除此之外，保证单个测试文件的 ∑n≦103 。
输出描述
输出 T 行，每行一个整数，表示长度为 n 的二进制串中，最大连续 1 的长度严格小于 r 的方案数(对 109+7 取模)。
样例1
输入
3
5 3
7 10
8 2
输出
24
128
55
