P10797 "CZOI-R1" Base

You have a number $x$, and you need to perform $n$ operations on it. In each operation, you may choose **one** valid digit of $x$ in base $y$ and increase its value by $1$. The first non-zero digit and all digits after it are considered valid digits. Note: * **For each operation**, you may choose any $y\in[2,+\infty)$. * You must ensure that the increment does not cause a carry in the base-$y$ representation of $x$. Now you need to find the maximum possible value of this number after $n$ operations. Output the answer in decimal, modulo $10^9+7$. You need to output the result of (the maximum value) modulo $10^9+7$, not the maximum value after taking modulo $10^9+7$.

**This problem has multiple test cases.** The first line contains an integer $T$, the number of test cases. The next $T$ lines each contain two integers $x,n$, representing the initial number and the number of operations.

For each test case, output one integer per line, representing the maximum value of $x$ after performing $n$ operations.

**[Sample Explanation]** Clearly, $2$ is $10$ in binary, and it is $2$ in base $3$ or higher. In binary, adding $1$ to the first digit would cause a carry, so you can only add $1$ to the second digit. The result is $11$, which is $3$ in decimal. In base $3$ or higher, you can only add $1$ to the last digit. In base $3$ it would cause a carry, so discard it. In base $4$ or higher, the result is always $3$, and the converted decimal result is also $3$. **[Constraints]** **This problem uses bundled testdata.** - Subtask #1 ($20\text{ pts}$): $x\le 2$. - Subtask #2 ($20\text{ pts}$): $n=1$. - Subtask #3 ($60\text{ pts}$): no special constraints. For $100\%$ of the testdata, $1\le x,n\le10^9$, and $1\le T\le10^6$. Translated by ChatGPT 5