Description

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$.

Input Format

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.

Output Format

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

2
1 2 1
3 2 1

2
7

Hint

[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