SP21458 NPC2014C - Satay Skewer

在「NPC 城」有许多餐馆，每家餐馆都有独特的招牌菜，因此这里成为了游客的热门景点之一。Joke 是个喜欢尝试各种食物的冒险家。某一天，他决定要品尝 NPC 城中所有的美食。由于 Joke 喜欢每家店的招牌菜，再加上时间飞逝，如今已是他于 NPC 城的最后一天参观。在这最后一天，Joke 决定去一家朋友推荐的餐馆，这家店名为「SaAn」（沙爹安达鲁）。SaAn 提供三种肉类的沙爹：鸡肉、羊肉和水牛肉。SaAn 的特别之处在于，每支沙爹上可以混合多种肉类。顾客可以根据自己的想法订购各种组合的沙爹。如果 SaAn 无法满足顾客的要求，那么顾客可以免费享用这顿餐。 了解到这个信息，Joke 想出了一个策略以享受免费美食。他给沙爹提出了一些具体要求： - 每串沙爹的第一块和最后一块肉都必须是鸡肉。 - 不允许出现连续的两块羊肉。 - 也不能出现连续的两块水牛肉。 - 每串沙爹中羊肉和水牛肉的总数不能超过 $K$。 - 每串沙爹的肉块数量总共为 $N$。 Joke 下单的沙爹数量即为满足以上条件的所有组合数。由于可能的组合数非常庞大，因此他将结果对 $1000000007$ 取模。 但是，Andaru 不愿意轻易提供免费食物，因此请你帮忙计算满足条件的沙爹数量是多少。

第一行包括一个整数 $T$，表示测试用例的数量。 接下来的每个测试用例包含两个整数 $N$ 和 $K$，分别表示肉块总数和羊肉或水牛肉的最大允许数量。

对于每个测试用例，输出满足条件的沙爹数量，对 $1000000007$ 取模后的结果。

+ $1 \le T \le 1000000$ + $0 \le N \le 1000$ + $0 \le K \le 100$ **本翻译由 AI 自动生成**