题目背景

注：数据已经加强。

题目描述

$T$ 次询问，每次给定 $A,B,C$，求：

$$\Big(\sum_{x=1}^A\sum_{y=1}^B\sum_{z=1}^C[y^x=x^z]\Big)\bmod (10^9+7). $$

输入格式

第一行一个正整数 $T$。

接下来 $T$ 行，每行三个正整数 $A,B,C$。

输出格式

$T$ 个整数 $\text{ans}$ 表示答案。以换行符隔开。

3
1 2 3
3 4 5 
6 7 8

3
8
15

2
999 9999 99999
2000 20000 200000

101202
202276

提示

【样例 1 解释】

第一组询问 $A=1,B=2,C=3$，满足条件的三元组 $(x,y,z)$ 有 $(1,1,1),(1,1,2),(1,1,3).$

第二组询问 $A=3,B=4,C=5$，满足条件的三元组 $(x,y,z)$ 有：

$(1,1,1),(1,1,2),(1,1,3),(1,1,4),(1,1,5),(2,2,2),(2,4,4),(3,3,3).$

第三组询问 $A=6,B=7,C=8$，满足条件的三元组 $(x,y,z)$ 有：

$(1,1,1),(1,1,2),(1,1,3),(1,1,4),(1,1,5),(1,1,6),(1,1,7),(1,1,8);$

$(2,2,2),(2,4,4),(3,3,3),(4,2,2),(4,4,4),(5,5,5),(6,6,6).$

---

【数据范围】

对 $100\%$ 的数据，满足 $1\leq T\leq 2\times 10^4,\ 1\leq A,B,C\leq 10^{18}$。

• $\text{Subtask}\ 0(5\ \text{pts})$：$T,A,B,C\leq 11$。
• $\text{Subtask}\ 1(7\ \text{pts})$： $T\leq 20,\ A,B,C\leq 3333$。
• $\text{Subtask}\ 2(17\ \text{pts})$：$T\leq 20,\ A,B\leq 10^{10},\ C\leq 3333$。
• $\text{Subtask}\ 3(17\ \text{pts})$：$T\leq 20,\ A,B,C\leq 10^{10}$。
• $\text{Subtask}\ 4(27\ \text{pts})$：$A,B,C\leq 10^{11}$。
• $\text{Subtask}\ 5(27\ \text{pts})$：无特殊限制。