题目描述

给定 $D,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}} $$

答案对 $10^9+7$ 取模。

输入格式

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

输出格式

输出 $T$ 个正整数，代表对应数据组答案。

输入输出样例

输入 #1

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

输出 #1

1
82488
510550839

说明/提示

数据规模与约定

本题采用捆绑测试。

• Subtask 1（2 pts）：$D,R,E,A,M\le10$。
• Subtask 2（41 pts）：$D,R,E,A,M\le100$
• Subtask 3（57 pts）：没有特殊限制。

对于所有数据，$1\le T\le2000$，$1\le D,R,E,A,M\le5\times10^7$。