1733. [SPOJ 2734] 盛大的派对

【题目描述】

Irena 和 Sirup 正在准备他们下周末的订婚派对。他们希望邀请几乎所有人。为此他们特地买了一张巨大的圆桌。但他们现在想要知道，应该如何给人们分配座位。Irena 声称，当有超过K位女士相邻时，她们就会闲聊一整晚，并且不会和其他任何人说话。

Sirup 不得不同意她的看法。但，作为一名数学家，他很快开始对所有男女在圆桌旁就坐的方案数感兴趣。

将有 $N$ 人坐在圆桌旁。其中的一些是男人，其余是女人。

你的任务是计算有多少种安排就坐的方式，使得没有超过 $K$ 名女士相邻。

如果某种就坐方案在旋转后与另外一种方案相同，我们就认为它们是同一个方案（因此只计算一次）。

【输入格式】

输入数据的第一行有一个整数 $T$，代表数据组数。

接下来是 $T$ 组数据。

每组数据有一行两个整数，$N（1<=N<=1000）$ 和 $K$。

对每组数据输出一个整数——安排人们就坐的方案总数，模 $100000007$。

【输出格式】

在此键入。

【样例输入】

3

3 1

3 3

4 1

【样例输出】

2

4

3

【提示】

对于第一组数据，有两种方案：MMM 或 MMW（M 代表男人，W 代表女人）。

对于第二组数据，除上面两种之外又多了两种方案：MWW 和 WWW。

对于第三种数据有三种方案：MMMM，MMMW 和 MWMW。

至多 1000 组数据。

数据为随机生成。

此处的数据范围和 SPOJ 原题略有不同，这里 $N$ 可以等于 $1000$.

【来源】

SPOJ 2734 Large Party