该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

这是不是公约数

题目描述

在一个古老的数学魔法森林中，三位传奇骑士——阿尔法、贝塔和西格玛，分别守护着三块神秘的魔法宝石。每块宝石都蕴含着强大的魔法力量，这力量由骑士的名字所代表的正整数 $a$、$b$、$c$ 决定。每当夜幕降临，魔法宝石便会释放出耀眼的光芒，其亮度分别由 $a^b - 1$ 和 $a^c - 1$ 来衡量。

然而，这片森林中隐藏着一柄神秘的剑，剑身上刻有 $10^9 + 7$ 这个神秘的数字，它能够吸收并封印魔法宝石的力量。数学森林的守护者们渴望知道，当这两束光芒经过神秘剑的封印后，它们的共同精华——最大公约数，将会剩下多少光辉。

现在，你被委以重任，要计算出这两束光芒共同精华的剩余力量，即 $gcd(a^b - 1,a^c - 1) \bmod (10^9 + 7)$，以维持森林的和谐与平衡。

输入格式

第一行一个正整数 $T$（$1 \le T \le 10^5$），表示数据组数。 接下来 $T$ 行，每行三个正整数 $a,b,c$（$2 \le a \le 10^9,1 \le b,c \le 10^9$）。

输出格式

输出 $T$ 行，表示每组数据的答案。

样例输入 1

3
2 3 4
6 9 10
233 666 999

样例输出 1

1
5
145107752

数据范围

• 对于30% 的数据，满足 $1 \le T \le 100$。
• 对于60% 的数据，满足 $1 \le T \le 1000$。
• 对于100% 的数据，满足 $1 \le T \le 10^5$，$2 \le a \le 10^9$，$1 \le b,c \le 10^9$。