2036：小球涂色

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

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

请计算有多少种可能的涂色方案，答案对 $10^9+7$ 取模。两种涂色方案是不同的，当且仅当存在一个 $1\le i\le n$，使得第 $i$ 个小球的颜色在两种涂色方案中不同。

第一行一个整数 $T$ 表示数据组数

对于每组数据，一行两个整数 $n,k$

$1\le T\le 20, 1\le n,k\le 10^5$

4
1 1
1 2
2 1
2 2

1
2
1
2