{"raw_statement":[{"iden":"problem statement","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$)."},{"iden":"constraints","content":"*   $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$"},{"iden":"input","content":"The 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."},{"iden":"sample input 1","content":"2\n20 8\n20 12"},{"iden":"sample output 1","content":"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."},{"iden":"sample input 2","content":"1\n20 3"},{"iden":"sample output 2","content":"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."},{"iden":"sample input 3","content":"1\n200 1"},{"iden":"sample output 3","content":"148322100\n\nNote that the value modulo $1000000007$ ( $10^9 + 7$ ) must be printed.\nThis case satisfies the constraint of the partial score."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}