P7108 Grafting and Transplanting

In a distant sacred land, there grows an unknown spirit tree, perhaps as tall as tens of thousands of mountains. But one day, the decayed power hidden in its roots erupted, and the spirit tree could no longer support its former towering height.

The spirit tree’s original form can be viewed as a full $a$-ary tree with height ${10}^{{10}^{{10}^{10}}}$. The height is defined as the number of edges from the root node to a leaf node. Affected by the decayed power, the spirit tree can only maintain the form of a full $b$-ary tree with height **exactly** $h$. To transform into this form, the spirit tree has two kinds of magic: - Transplanting: choose an edge $u \to v$ ($u$ is the parent of $v$), remove this edge and the **entire subtree** rooted at $v$. - Grafting: choose an edge $u \to v$ ($u$ is the parent of $v$) and a node $w$ ($w$ cannot be in the subtree of $v$ or a node that has been removed), and reattach the endpoint at $u$ of this edge to $w$. **This magic can only be used when the number of edges from the root node to** $\boldsymbol{u}$ **is** $\le 10^{10^{10}}$. The spirit tree has limited accumulated magical power, so it must complete the transformation using the minimum number of spells. This is a long process: even the minimum number can be extremely large. You only need to compute the minimum number modulo $10^9 + 7$.

The first line contains the number of test cases $T$. The next $T$ lines each contain three integers $a, b, h$, describing one test case.

For each test case, output one integer per line, the answer modulo $10^9 + 7$.

**[Sample Explanation #1]** Below is the two-step transformation process for $a=1$, $b=2$, $h=1$. The extremely tall redundant subtrees in the figure are replaced by ellipses.  It can be proven that the answer for this test case cannot be less than $2$. ---- **[Constraints and Notes]** **This problem uses bundled tests**. You must pass all test points in a Subtask to obtain the score for that Subtask. - Subtask #1 (3 points): $h = 0$. - Subtask #2 (4 points): $a = b$. - Subtask #3 (8 points): $a = 1$. - Subtask #4 (8 points): $b = 1$. - Subtask #5 (17 points): $h \le 10$. - Subtask #6 (15 points): $h \le 10^6$. For each test point, there exist $\overline{a}, \overline{b}$ such that the testdata satisfy $a=\overline{a}$ and $b=\overline{b}$. - Subtask #7 (15 points): $h \le 10^6$. - Subtask #8 (30 points): no special restrictions. All test points (except the samples) contain $10^6$ test cases, i.e. $T = 10^6$. Be sure to use fast I/O methods. For all test cases, it is guaranteed that $1 \le a,b \le 10^9$ and $0 \le h \le 10^9$. Translated by ChatGPT 5