题目描述

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

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

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

输入格式

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

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

输出格式

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

4
1 1
1 2
2 1
2 2

1
2
1
2

数据范围

对于 $30\%$ 的数据，$n\leq k\leq 10$。

对于 $60\%$ 的数据，$n\leq k$。

对于 $100\%$ 的数据，$1\leq T\leq 20$，$1\leq n,k\leq 10^5$。