公约数
题目背景
在收卷最后五分钟,pg发现了卷子反面还有一道大题。
题解:https://blog.csdn.net/kkkksc03/article/details/85008136
题目描述
求
[![](https://cdn.luogu.com.cn/upload/pic/33775.png)](https://www.luogu.org/paste/zltm8ddt)
由于答案可能过大,输出答案对$10^9+7$取模的值。
输入输出格式
输入格式
第一行一个正整数$T$,为数据组数。
下面$T$行,每行$3$个整数,为$n,m,p$。
输出格式
共$T$行,每行一个整数,为答案。
输入输出样例
输入样例 #1
2
10 12 11
30 20 25
输出样例 #1
25302
573830
说明
前$10\%$的数据,$T=5~,~40 \le n,m,p \le 100.$
对于另外$20\%$的数据,$T=50~,~100 \le n,m,p \le 5\times 10^4.$
对于另外$20\%$的数据,$T= 20~,~4\times 10^6 \le n,m,p \le 5\times 10^6$
对于另外$50\%$的数据,$T=10^3~,~10^7 \le n,m,p \le 2\times 10^7$