Handing out leaflets

AtCoder

IDkupc2016_i

Time1000ms

Memory256MB

Difficulty—

Eli- $1$ started a part-time job handing out leaflets for $N$ seconds. Eli- $1$ wants to hand out as many leaflets as possible with her special ability, Cloning. Eli- $gen$ can perform two kinds of actions below. * Clone herself and generate Eli- $(gen + 1)$ . (one Eli- $gen$ (cloning) and one Eli- $(gen + 1)$ (cloned) exist as a result of Eli-$gen$ 's cloning.) This action takes $gen \times C$ ( $C$ is a coefficient related to cloning. ) seconds. * Hand out one leaflet. This action takes one second regardress of the generation ( $=gen$ ). They can not hand out leaflets while cloning. Given $N$ and $C$ , find the maximum number of leaflets Eli- $1$ and her clones can hand out in total modulo $1000000007$ ($= 10^9 + 7$). ## Constraints * $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$ ## Input The input is given from Standard Input in the following format: $Q$ $N_1$ $C_1$ : $N_Q$ $C_Q$ The input consists of multiple test cases. On line $1$ , $Q$ that represents the number of test cases is given. Each test case is given on the next $Q$ lines. For the test case $q$ ( $1 \leq q \leq Q$ ) , $N_q$ and $C_q$ are given separated by a single space. $N_q$ and $C_q$ represent the working time and the coefficient related to cloning for test case $q$ respectively. [samples]

Samples

Input #1

2
20 8
20 12

Output #1

24
20

For the first test case, while only $20$ leaflets can be handed out without cloning, $24$ leaflets can be handed out by cloning first and two people handing out$12$ leaflets each.
For the second test case, since two people can only hand out $8$ leaflets each if Eli- $1$ clones, she should hand out $20$ leaflets without cloning.

Input #2

1
20 3

Output #2

67

One way of handing out 67 leaflets is like the following image. Each black line means cloning, and each red line means handing out.

![image](/img/other/kupc2016/sushi/sample2.png)

This case satisfies the constraint of the partial score.

Input #3

1
200 1

Output #3

148322100

Note that the value modulo $1000000007$ ( $10^9 + 7$ ) must be printed.
This case satisfies the constraint of the partial score.

API Response (JSON)

{
  "problem": {
    "name": "Handing out leaflets",
    "description": {
      "content": "Eli- $1$ started a part-time job handing out leaflets for $N$ seconds. Eli- $1$ wants to hand out as many leaflets as possible with her special ability, Cloning. Eli- $gen$ can perform two kinds of ac",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "kupc2016_i"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Eli- $1$ started a part-time job handing out leaflets for $N$ seconds. Eli- $1$ wants to hand out as many leaflets as possible with her special ability, Cloning. Eli- $gen$ can perform two kinds of ac...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments