题目描述

Irena 和 Sirup 正准备下个周末的 Party。为这个 Party，他们刚刚买了一个非常大的圆桌。他们想邀请每个人，但他们现在不知道如何分配座次。Irena 说当有超过 $K$ 个女孩座位相邻（即这些女孩的座位是连续的，中间没有男孩）的话，她们就会说一整晚的话而不和其他人聊天。

Sirup 没有其他选择，只有同意她。然而，作为一名数学家，他很快地痴迷于所有可能方案。

你可能已经知道了，Sirup 无法解决这个问题，于是他来求助你，你的任务是找出方案数 $ans$， Sirup 只对方案数 $ans \mod 100000007$ 感兴趣，所以请你输出 $ans \mod 100000007$ 的值。

输入格式

第一行有一个数 $T$，表示以下有 $T$ 组数据，每组数据有两个整数 $N$，$K$。

每组数据之间有一个空行隔开。

输出格式

输出 $T$ 行，每行顺次对应一组测试数据。

每组数据你需要输出最后的方案数除以 $100000007$ 的余数。

样例输入

3
3 1
3 3
4 1

样例输出

2
4
3

样例解释

第一组数据的方案是：MMM，MMW (M是男孩, W是女孩)。

第二组数据的方案是：MMM，MMW，MWW，WWW。

第三组数据的方案是：MMMM, MMMW,MWMW。

数据规模及约定

对于 $20 \%$ 的数据 $1 \le T \le 20$，$1 \le N,K \le 20$；

对于 $100 \%$ 的数据 $1 \le T \le 50$，$1 \le N,K \le 2 \times 10^3$。

题目来源

HNOI2009 集训 Day4

2008 Large Party