题目描述

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

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

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

输入格式

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

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

输出格式

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

样例 #1

4
1 1
1 2
2 1
2 2

1
2
1
2

提示

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