AT_kupc2016_i.ティッシュ配り

Eli- $1$ 先生决定做一份持续 $N$ 秒的发放纸巾的兼职工作。Eli- $1$ 先生拥有一种特殊能力——分身，他打算利用这一能力尽可能多地发放纸巾。Eli- $gen$ 先生可以进行以下两种操作：

• 花费 $gen \times C$ 秒，将自己分身为 Eli- $gen$ 先生和 Eli- $(gen+1)$ 先生两人。
• 无论是哪一代（即 $gen$ 的值），都可以花费 $1$ 秒发放恰好 $1$ 张纸巾。

不能在发放纸巾的同时进行分身。给定 $N$ 和 $C$，请你计算 Eli- $1$ 先生和所有分身合计最多能发放多少张纸巾。由于答案可能非常大，请输出对 $1000000007$（即 $10^9+7$）取模后的结果。

输入由多组查询组成。

第一行包含一个整数 $Q$，表示查询的个数。

接下来的 $Q$ 行，每行包含两个用半角空格分隔的整数 $N_q$ 和 $C_q$，分别表示第 $q$ 个查询的工作时间和分身所需时间的系数。

对于每个查询，输出 Eli- $1$ 先生和所有分身合计最多能发放的纸巾数量。由于答案可能非常大，请输出对 $1000000007$（即 $10^9+7$）取模后的结果。

限制

• $1 \leq Q \leq 100000 = 10^5$
• $1 \leq N_q \leq 100000 = 10^5$
• $1 \leq C_q \leq 20000 = 2 \times 10^4$

部分得分

如果你能正确解决 $Q=1$ 的数据集，可以获得 $30$ 分的部分分数。

如果你能正确解决没有额外限制的数据集，可以再获得 $270$ 分，总分为 $300$ 分。

样例解释 1

对于第一个查询，如果不分身只能发放 $20$ 张纸巾，而分身后两个人各发放 $12$ 张，可以发放 $24$ 张纸巾，这是最大值。对于第二个查询，如果分身后两个人各发放 $8$ 张纸巾，还不如不分身直接发放 $20$ 张。

样例解释 2

可以按照下图进行操作。黑线表示分身，红线表示发放纸巾。 这个案例满足部分分数的额外限制。

样例解释 3

请注意需要对 $1000000007$（$10^9+7$）取模。这个案例满足部分分数的额外限制。

由 ChatGPT 4.1 翻译