有一天，Homer 在家里感到无聊，决定去探索 Springfield 的土地。Springfield 的土地是一个无限大的网格。Homer 的家位于 $(0, 0)$，他的旅程由 $N$ 步组成，每一步要么向右移动一格，要么向下移动一格。

由于已经感到无聊，Homer 不希望他的旅程也变得枯燥。他决定在同一个方向上连续移动的步数不会超过 $K$ 步。因此，如果对于任意连续的 $K+1$ 步，Homer 在这两个方向上都有移动，那么这段旅程就被认为是“有趣的”。

图 1：$N=5$ 且 $K=2$ 的示例（第一个测试用例）。

给定 $N$ 和 $K$，计算 Homer 可以进行的有趣旅程的数量。如果两个旅程在某一步 $i$ 的移动方向不同，则认为这两个旅程是不同的。由于数字可能很大，请输出其对 $1,000,000,007$ 取模的结果。

输入格式

程序将在一个或多个测试用例上进行测试。输入的第一行是一个整数 $T$，表示测试用例的数量 $(1 \le T \le 500)$，随后是 $T$ 个测试用例。

每个测试用例由一行组成，包含两个由空格分隔的整数。第一个整数表示 Homer 旅程的步数 $N$，第二个整数 $K$ 表示 Homer 在同一方向上移动时可以采取的最大连续步数，其中 $(0 \le N \le 10^5)$ 且 $(0 \le K \le 10^5)$。

输出格式

对于每个测试用例，输出一行，表示 Homer 可以进行的有趣旅程的数量，对 $1,000,000,007$ 取模。

样例

样例输入 1

2
5 2
10 1

样例输出 1

16
2