EOJ Monthly 2019.5 (based on May Selection)

B. 幂运算

单点时限: 1.0 sec

内存限制: 256 MB

QQ小方以前不会幂的运算,现在他会了,所以他急切的想教会你。

对于形如 $x^a$ 的计算,可以归结到乘法运算 $x^a=\prod _{1}^{a} x$ 。

单单讲给你听肯定是不够的,为了表现自己,QQ小方现在要考考你。

QQ小方现在想知道有多少四元组 $(a,b,c,d)$ ( $1\le a,b,c,d, a \le a_{max}, b \le b_{max}, c \le c_{max}, d \le d_{max} $ )满足 $a^b=c^d$ ,答案对 $10^9+7$ 取模。

输入格式

输入数据第一行包含一个整数 $T (1\le T\le 100)$ ,表示数据组数。

每组数据包含一行, 四个整数 $a_{max}, b_{max}, c_{max}, d_{max}$ ( $1 \le a_{max}, b_{max}, c_{max}, d_{max} \le 10^9$ ),含义如题目所述。

输出格式

对于每一组数据,输出一行包含一个整数表示答案,答案对 $10^9+7$ 取模。

样例

Input
2
2 3 4 5
10 10 10 10
Output
19
222