分数: 300 点
问题陈述
Eli- 1 开始了一份发传单的兼职工作 N 秒。 伊莱- 1 想利用她的特殊能力“克隆”来分发尽可能多的传单。 伊莱- gen 可以执行以下两种操作。
- 克隆自己并生成Eli- (gen + 1) 。 (一个伊莱- gen (克隆)和一个 Eli- (gen + 1) (克隆)由于Eli-而存在gen 的克隆。) 这个动作需要 gen \times C ( C 是与克隆相关的系数。 )秒。
- 分发一张传单。这一行动需要一代人的一秒钟的关注( =gen ).
他们不能在克隆时分发传单。 给定 N 和 C ,找到传单的最大数量 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 N_1 C_1 : N_Q C_Q
输入由多个测试用例组成。上线 给出了表示测试用例数量的 1 , Q 。 每个测试用例都在下一个给出 Q 行。 对于测试用例 q ( 1 \leq q \leq Q ) , N_q 和 C_q 用一个空格分隔。 N_q 和 C_q 代表测试用例的工作时间和克隆相关系数 分别为 q 。
输出
对于每个测试用例,打印传单的最大数量 Eli- 1 和她的克隆人可以分发模数 1000000007 ( = 10^9 + 7 ).
部分分数 通过满足条件的测试集将获得
30 积分: Q = 1 .
另一个 270 分数将在没有额外限制的情况下通过测试集而获得,您可以获得 总共 300 分。
示例输入 1
2 20 8 20 12
示例输出 1
24 20
对于第一个测试用例,虽然只有 20 传单无需克隆即可分发, 24 传单可以先克隆再两人分发12 传单各一份。
对于第二个测试用例,由于两个人只能分发 8 传单,如果 Eli- 1 克隆人,她应该分发 20 没有克隆的传单。
示例输入 2
1 20 3
示例输出 2
67
分发 67 张传单的一种方式如下图所示。每条黑线意味着克隆,每条红线意味着分发。
这种情况满足部分分数的约束。
示例输入 3
1 200 1
示例输出 3
148322100
请注意,该值模 必须打印 1000000007 ( 10^9 + 7 )。
这种情况满足部分分数的约束。