{"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 actions below.\n\n*   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.\n*   Hand out one leaflet. This action takes one second regardress of the generation ( $=gen$ ).\n\nThey 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$).\n\n## Constraints\n\n*   $1 \\leq Q \\leq 100000 = 10^5$\n*   $1 \\leq N_q \\leq 100000 = 10^5$\n*   $1 \\leq C_q \\leq 20000 = 2 \\times 10^4$\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$Q$\n$N_1$ $C_1$\n:\n$N_Q$ $C_Q$\n\nThe 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.\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"kupc2016_i","tags":[],"sample_group":[["2\n20 8\n20 12","24\n20\n\nFor 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.\nFor 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."],["1\n20 3","67\n\nOne way of handing out 67 leaflets is like the following image. Each black line means cloning, and each red line means handing out.\n\n![image](/img/other/kupc2016/sushi/sample2.png)\n\nThis case satisfies the constraint of the partial score."],["1\n200 1","148322100\n\nNote that the value modulo $1000000007$ ( $10^9 + 7$ ) must be printed.\nThis case satisfies the constraint of the partial score."]],"created_at":"2026-03-03 11:01:14"}}