SP20196 DIVEQL - The Magical Bag

Dukkar 拥有一个神奇的袋子，其神奇之处在于袋子的“魔力值”为 **P**。这意味着任何放入袋子里的东西，数量都会在下一步变为原来的 **P** 倍。 现在，Dukkar 希望利用这个魔袋子将巧克力平均分给他的 **N** 个学生： 开始时，Dukkar 手中有 **Z** 块巧克力。他将其中的 **X** 块分给第一个学生，并把剩下的巧克力放入神奇的袋子，这样在下一步它们的数量变为 **P** 倍。接下来，他再从袋子里拿出 **X** 块巧克力给第二个学生，剩下的巧克力数量在下一步同样会变成 **P** 倍。这个过程一直持续下去。 你的任务是找到最小的 **Z**，使得在最后一步分给最后一个学生 **X** 块巧克力后，袋子里不再有剩余的巧克力。

输入的第一行包含一个整数 **T**，表示测试用例的数量（**T** < 100000）。接下来的 **T** 行，每行包含两个整数 **N** 和 **P**，表示学生人数和袋子的魔力值。

对于每个测试用例，输出最小的 **Z** 和对应的 **X**。由于结果可能非常大，请输出模 1000000007 以后的结果。 (即 Z % 1000000007 和 X % 1000000007) ## 示例 **输入：** ``` 1 3 2 ``` **输出：** ``` 7 4 ``` **解释：** 设定 Z = 7，开始时，Dukkar 分给第一个学生 4 块巧克力，袋子里剩余 3 块。在下一步中，这 3 块巧克力变为 6 块，然后他又分给第二个学生 4 块。在下一步中，剩下的 2 块巧克力变成 4 块，最后全部分给第三个学生。此时袋子已经空了。 ## 数据范围 - 1 ≤ T < 100000 - 2 ≤ N ≤ 10^18 - 2 ≤ P ≤ 10^9 **本翻译由 AI 自动生成**