#H1070. 绝世傻逼题 · REMATCH

绝世傻逼题 · REMATCH

题目描述

给定 D,R,E,A,MD,R,E,A,M,求:

$$\newcommand{\lcm}{\operatorname{lcm}}\sum_{d=1}^D\sum_{r=1}^R\sum_{e=1}^E\sum_{a=1}^A\sum_{m=1}^M\frac{\begin{matrix}\gcd(d,r,e)\gcd(d,r,a)\gcd(d,r,m)\gcd(d,e,a)\gcd(d,e,m)\\\gcd(d,a,m)\gcd(r,e,a)\gcd(r,e,m)\gcd(r,a,m)\gcd(e,a,m)\end{matrix}}{\begin{matrix}\gcd(\lcm(d,r),\lcm(d,e),\lcm(d,a),\lcm(d,m),\\\lcm(r,e),\lcm(r,a),\lcm(r,m),\lcm(e,a),\lcm(e,m),\\\lcm(a,m))^3\gcd(\lcm(d,r,e),\lcm(d,r,a),\lcm(d,r,m),\\\lcm(d,e,a),\lcm(d,e,m),\lcm(d,a,m),\lcm(r,e,a),\\\lcm(r,e,m),\lcm(r,a,m),\lcm(e,a,m))\end{matrix}} $$

答案对 109+710^9+7 取模。

输入格式

本题输入含有多组数据。 第一行一个正整数 TT,代表数据组数量。 接下来 TT 行,每行五个正整数,分别代表 D,R,E,A,MD,R,E,A,M

输出格式

输出 TT 个正整数,代表对应数据组答案。

输入输出样例

输入 #1

3
1 1 1 1 1
5 6 7 8 9
5642228 7263010 8833976 5087685 6171346

输出 #1

1
82488
510550839

说明/提示

数据规模与约定

对于所有数据,1T501\le T\le501D,R,E,A,M1091\le D,R,E,A,M\le10^9