Hang的数学题

每一场比赛都是需要签到题的，每一道签到题的背后都有一位良心出题人，总所周知，工院的有个只会出水题的Hang，所以出签到题的伟大任务又扔给他了，良心出题人Hang保证这题是这场我出的最简单的一题，没有之一

为了能让所有人都能够签到，Hang特意为基础较差的萌新引用一道简单题目，方便所有人AC

首先，假设你有一只兔子

接着，我再给你一只兔子

最后，数一下你有的兔子数量，你发现你有了两只兔子。由此我们发现，一只兔子加一只兔子等于两只兔子，也就是1+1=2

那么现在，你已经对算术的基本原理有了一定了解，就让我们来看一看下面这道简单的签到题吧，把我们刚刚学到的知识运用到实践中吧

既然是签到题，题目当然就很简单了，Hang想知道，对于1<=a,b,c,d<=n，有多少组a,b,c,d，满足a^c=b^d

^{出题人用脚写的题解：https://www.cnblogs.com/rainH/p/10822746.html}

第一行是一个t，表示t组数据

接下来t行，每行一个数正整数n

对于30%数据:t<12,(1<=n<=12)（这么简单？）

对于70%数据:t=1000,（1<=n<1000000）(1e6)（我擦嘞？）

对于90%数据:t=1000,(1<=n<=10001000000000)(1e9)（什么玩意？）

对于100%数据:t=2000,(1<=n<=10001000000000000)(1e12)（别骂脏话，要文明）

虽然好像1000你也不会做

这数据范围良心吧，所有n都随机生成，不特意卡常

这题有人能签上就见鬼了

输出共有t行，每行一个整数，表示最后答案，因为这个数可能会比较大，所以取模1000000007（1e9+7）即可

3
1
2
3

1
6
15

以下为输出提示：
对于n=2的数据
abcd存在以下6种情况
1 1 1 1
1 1 2 2
1 1 2 1
1 1 1 2
2 2 1 1
2 2 2 2