题目背景

遥远的圣地生长着一棵不为人知的灵树，或有万山之高。

但有一日，藏匿于根系的腐朽力量爆发，灵树已无法支撑往日屹立冲天的高度。

题目描述

灵树最初的形态可以看作一棵高度为 ${10}^{{10}^{{10}^{10}}}$ 的满 $a$ 叉树，高度定义为根结点到叶子结点之间的边数。

受腐朽力量影响，灵树只能维持高度恰好为 $h$ 的满 $b$ 叉树形态。为了转换至该形态，灵树有两种魔法：

• 移花：选择一条边 $u \to v$（$u$ 是 $v$ 的父结点），移除这条边以及以 $v$ 为根的整棵子树。
• 接木：选择一条边 $u \to v$（$u$ 是 $v$ 的父结点）和一个结点 $w$（$w$ 不能是 $v$ 子树中或已移除的结点），将这条边原先 $u$ 一端改接到 $w$。该魔法只能在根结点到 $\boldsymbol{u}$ 之间的边数 $\le 10^{10^{10}}$ 时使用。

灵树累积的魔法力量有限，它不得不用最少次数的魔法完成转换。这是个漫长的过程，即使次数最少也会显得异常大，你只需要求出最少次数对 $10^9 + 7$ 取模的结果。

输入格式

输入首行给定数据组数 $T$。

接下来 $T$ 行，每行包含三个整数 $a,b,h$，表示一组数据。

输出格式

对于每组数据输出一行一个整数，表示该数据的答案对 $10^9 + 7$ 取模的结果。

2
1 2 1
3 2 1

2
7

提示

【样例解释 #1】

下为 $a=1$，$b=2$，$h=1$ 时的两步转换过程，图中高度极大的冗余子树已用省略号代替。

可以证明，该数据的答案不可能低于 $2$。

【数据规模与约定】

本题采用捆绑测试。你必须通过 Subtask 中所有的测试点才能获得该 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$，各测试点存在 $\overline{a},\overline{b}$，其数据满足 $a=\overline{a}$，$b=\overline{b}$。
• Subtask #7 (15 points)：$h \le 10^6$。
• Subtask #8 (30 points)：无特殊限制。

所有测试点（样例除外）均含有 $10^6$ 组数据，即 $T = 10^6$。请务必采用较快的 IO（输入/输出）方式。

对于所有的数据，保证 $1 \le a,b \le 10^9$，$0 \le h \le 10^9$。