周末晚会

Irena 和 Sirup 正在为下个周末的晚会做准备。他们刚买了一张非常大的圆桌，并打算邀请大家参加，但还没有决定如何安排座位。

Irena 认为，如果有超过 $K$ 个女孩连续坐在一起，即这些女孩之间没有男孩，那么她们就会整晚只顾彼此交谈，而不与其他人聊天。Sirup 只好同意这一要求。作为一名数学家，他很快对所有可能的座位方案产生了兴趣。

共有 $N$ 个人围坐在圆桌旁，每个座位上坐的是男孩或女孩。请计算满足任意连续女孩人数均不超过 $K$ 的座位方案数。

通过旋转可以相互重合的方案视为同一种方案。

输入格式

第一行包含一个整数 $T$，表示测试数据的组数。

接下来有 $T$ 组测试数据，每组包含两个整数 $N$ 和 $K$。相邻两组测试数据之间有一个空行。

输出格式

输出 $T$ 行，每行对应一组测试数据，表示合法方案数对 $10^8+7$ 取模后的结果。

样例输入

3

3 1

3 3

4 1

样例输出

2
4
3

样例解释

在以下方案中，$M$ 表示男孩，$W$ 表示女孩。

第一组数据的合法方案为：MMM、MMW。

第二组数据的合法方案为：MMM、MMW、MWW、WWW。

第三组数据的合法方案为：MMMM、MMMW、MWMW。

数据范围

• 对于 $20\%$ 的数据，$T\le 20$；
• 对于全部数据，$T\le 50$；
• 对于 $20\%$ 的数据，$N,K\le 20$；
• 对于全部数据，$N,K\le 2000$。

来源与许可

本题题面与测试数据整理自 BZOJ。

样例 1

输入

3

3 1

3 3

4 1

输出

2
4
3