SP14032 VPL1_AB - Summer Game

贝托、迪基、路易斯、马克斯、查理和里奇特别喜欢在夏天玩一些疯狂的游戏，可以在任何社交网络上找到。他们在游戏时会喝一种叫做「Aquameister」的奇怪饮料，喝多了会让人头晕！贝托对每次都输掉比赛感到厌倦，但查理却是最能抵抗这些挑战的人。于是，贝托向你求助，希望在他自己晕倒前让查理先头晕！游戏的目标显而易见，就是获胜，并且游戏由一个长长的行构成，贝托从位置 1 开始。 在游戏中，每个位置你都必须喝一小杯 Aquameister。如果他在当前回合掷出与上一个回合相同的骰子组合，他需要再喝一杯。为了简化问题，我们定义“相同动作”为掷出了与上次完全相同的骰子组合。例如，如果贝托掷出了 (2,1,2)，那么他可以掷出 (1,2,2)，不能再掷 (2,1,2)。游戏一直进行，直到贝托到达位置 $N$。如果在最后一个位置贝托晕倒了，游戏将失败，他必须再喝两杯并重新开始。但为了贝托的好处，如果他晕倒，这次只需再喝两杯就可以结束。 贝托想知道，有多少种不同的方法可以完美地结束游戏，即从位置 1 到达位置 $N$。因为结果可能非常大，因此请输出答案对 $1,000,000,007$ 取模的结果。

第一行输入一个整数 $T$，表示测试用例的数量。接下来的每个测试用例包括两个整数 $N$ 和 $D$，分别表示行的长度和每轮要掷出的骰子数量（每个骰子为六面）。

对于每个测试用例，输出格式为 `Scenario #i:`，其中 $i$ 表示测试用例的编号（从 1 开始），接着是问题的答案。 **输入示例** ``` 3 3 1 4 1 6 1 ``` **输出示例** ``` Scenario #1: 1 Scenario #2: 3 Scenario #3: 7 ```

- **子任务 1 (10%)** - $1 \le T \le 1$ - $1 \le N \le 10$ - $1 \le D \le 1$ - **子任务 2 (30%)** - $1 \le T \le 10$ - $1 \le N \le 100$ - $D = 1$ - **子任务 3 (60%)** - $1 \le T \le 100$ - $1 \le N \le 1000$ - $1 \le D \le 6$ **本翻译由 AI 自动生成**