小球涂色

题目描述

有 $n$ 个小球排成一行，依次从 $1$ 到 $n$ 编号，你需要用 $k$ 种颜色给它们涂色。

为了涂色后看起来不那么单调，你希望任意距离小于 $k$ 的小球不同色。换言之，如果 $1 \leq i, j \leq n$，$|j - i| < k$，第 $i$ 个小球和第 $j$ 个小球不能涂相同的颜色。

请计算有多少种可能的涂色方案，答案对 $10^9 + 7$ 取模。

输入格式

第一行一个整数 $T$ 表示数据组数。对于每组数据，一行两个整数 $n, k$。

输出格式

对于每组数据，输出一行一个整数表示答案。

数据范围

• $1 \leq T \leq 20$，$1 \leq n, k \leq 10^5$

样例

样例输入

4
1 1
1 2
2 1
2 2

样例输出

1
2
1
2