SP19545 BWB - Black and White beads

有很多珠子，颜色分为白色和黑色两种。你需要把这些珠子按顺序串成一条项链，但要遵循一些限制条件。首先，不能有连续的 $K$ 个黑色珠子，并且项链的第一个珠子必须是白色的。现在的问题是，找出所有满足这些条件的长度为 $N$ 的项链组合个数。

第一行是一个整数 $T$，表示测试用例的数量。接下来的 $T$ 行，每行包含两个整数 $N$ 和 $K$，分别表示项链的长度和限制条件。

对于每个测试用例，输出一行，表示满足条件的项链组合数对 $1000000007$ 取模后的结果。

- $1 \le T \le 1000000$ - $1 \le N \le 10000$ - $1 \le K \le 100$ **样例输入** ``` 3 2 3 2 1 4 2 ``` **样例输出** ``` 2 1 8 ``` **样例解释** 对于第一个测试用例，即 $N=2$ 和 $K=3$，不允许有三个连续的黑珠子。符合条件的项链组合为「白-白」和「白-黑」。注意，「黑-白」是不符合条件的组合，所以答案为 $2$。 **本翻译由 AI 自动生成**