2674: 高三楼

参观完各种饭堂，学校还有什么著名的景点呢？当然是教室了，此时此刻我们来到了高三楼。你会发现高三楼门口会有以身份认证系统，这东西还有着一段疼人的历史。

每年的九月到来，高三的童鞋大多不习惯学校的作息时间，有人迟到的情况在所难免，2013届的moreD同志作为当年的纪检部部长，创造了一种十分厉害的身份认证系统。他会给每位童鞋的饭卡加上一个电子认证信息：一个n*n的矩阵，其中，每行每列都有两个特殊的点。moreD同志设计的身份认证系统会把这些矩阵读进来，并且对此进行解析，由于每个同学都带有独特的矩阵，系统就可以在0.00001s内认证出童鞋的身份。这样迟到的童鞋被登记的速度就会加快（刷卡嘛），大家上课的时间就不会耽误了，简单、快捷、方便统计。这一切都要感谢moreD神牛。

但是，有一个IQ超高的，经常迟到的童鞋，为了不扣分，他破解了moreD的身份认证系统，并对自己的认证信息做了更改。moreD得知这个消息后立即对此等不良bug进行改进。

他发现对于一些矩阵，只要把与之“重复”的矩阵取出，假身份认证信息的制造率会降低很多。

“重复”的定义为矩阵a，通过任意次行列变换，变成了矩阵b，矩阵a,b就视为重复。

例如：对于3*3的矩阵，其中矩阵a与矩阵b被视为“重复”矩阵。

X				X		X			X	X
X				X	X			X		X
X	X	X			X	X		X	X

不合法矩阵 矩阵a 矩阵b

moreD想知道对于一个n，可以有多少种不“重复”的矩阵，来填写不同学生的信息，moreD忙着更改身份认证系统，这个艰巨的任务就交给你了,你只需要输出答案mod 100000007的值就可以了，因为高一的学生可没有这么多。

第一行，一个整数t，表示数据组数。

接下来t行，每行一个整数n，表示一组数据。

T行，每行一个整数，表示方案数。由于答案可能很大，只需要输出方案数mod 100,000,007 的值就可以了。

3
2
3
4

1
1
2