D. Tangjz 的背包

你有 个候选物品，你想要从中选出 个物品放进体积为 的背包里。

在选择物品时，你发现这些候选物品的体积分别为 ，于是你想知道有多少种选法可以恰好将体积为 的背包填满。

注意，两种选法不同当且仅当存在至少一个候选物品只在某一种选法中被选择。

为了便于输出，我们假设从这样的 个候选物品里选出 个物品填满体积为 的背包有 种选法，并令 为使得 不为 的最大正整数，你只需要输出 的值即可。显而易见的是当 时一定存在这样的 。

第一行包含一个正整数 ，表示有 组测试数据。

接下来依次给出每组测试数据，每组测试数据仅两行，包含两个正整数 和 ，含义如题目所示。

对于每组测试数据，输出一行，包含一个整数，表示题目中要求输出的值。

样例输入 1

1
3 2

样例输出 1

238284724

样例解释 1

对于该组样例，，其他 都为 ，所以有 。

样例输入 2

1
4 2

样例输出 2

186699913

样例解释 2

对于该组样例，，其他 都为 ，所以有 。

对于所有数据， 。