← 返回题目列表

AtCoder · kupc2016_i

I. 散发传单

中文机器翻译题面 查看原题

分数: 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 )。

这种情况满足部分分数的约束。