单点时限: 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$ 取模。
2 2 3 4 5 10 10 10 10
19 222