### 问题描述 在一个没有光线的房间里，有 $N$ 个人从左到右依次编号为 $1$ 到 $N$。有 $K$ 种颜色不同的帽子，每种帽子的数量无限多，现在需要为每个人戴上一个帽子，共有 $k^n$ 种不同的戴帽子方案。然而，现在有一个限制条件：如果两个人的编号之差的绝对值小于 $K$，那么他们戴的帽子颜色不能相同。现在需要计算满足限制条件的戴帽子方案数，答案需要对 $10^9+7$ 取模。 ### 输入格式 第一行输入一个整数 $T$ ，表示询问的次数。 对于每次询问，输入一行数据两个整数 $N$ 和 $K$ 。 数据范围保证：$1 \leq T \leq 10000$，$1\leq N,K \leq 100$。 ### 输出格式 对于每次询问输出一行一个整数表示答案，答案需要对 $10^9+7$ 取模。 ### 样例输入 ```text 2 2 1 2 2 ``` ### 样例输出 ```text 1 2 ``` ### 说明 用数字表示帽子的颜色。 在第一个询问中，两个人都戴编号为 $1$ 的帽子，只有一种方案。 在第二个询问中，第一个人戴 $1$ 号帽子，第二个戴 $2$ 号帽子，两者交换帽子后也合法，有两种方案。