参观完各种饭堂，学校还有什么著名的景点呢？当然是教室了，此时此刻我

们来到了高三楼。你会发现高三楼门口会有以身份认证系统，这东西还有着一段
疼人的历史。
每年的九月到来，高三的童鞋大多不习惯学校的作息时间，有人迟到的情况
在所难免，2013 届的moreD 同志作为当年的纪检部部长，创造了一种十分厉
害的身份认证系统。他会给每位童鞋的饭卡加上一个电子认证信息：一个n*n
的矩阵，其中，每行每列都有两个特殊的点。moreD 同志设计的身份认证系统
会把这些矩阵读进来，并且对此进行解析，由于每个同学都带有独特的矩阵，系
统就可以在0.00001s 内认证出童鞋的身份。这样迟到的童鞋被登记的速度就会
加快（刷卡嘛），大家上课的时间就不会耽误了，简单、快捷、方便统计。这一
切都要感谢moreD 神牛。
但是，有一个IQ 超高的，经常迟到的童鞋，为了不扣分，他破解了moreD
的身份认证系统，并对自己的认证信息做了更改。moreD 得知这个消息后立即
对此等不良bug 进行改进。
他发现对于一些矩阵，只要把与之“重复”的矩阵取出，假身份认证信息的制造
率会降低很多。
“重复”的定义为矩阵a，通过任意次行列变换，变成了矩阵b，矩阵a,b
就视为重复。
例如：对于3*3 的矩阵，其中矩阵a 与矩阵b 被视为“重复”矩阵。


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

输入格式：

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

输出格式：

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

样例输入：

3

2

3

4

样例输出：

1

1

2

数据范围：

对于10%的数据 N≤5；
对于50%的数据 N≤150；
对于100%的数据T≤5 N≤2,000。

时间限制：

1S

空间限制：

256M

#include <bits/stdc++.h>

#define mod 100000007

using namespace std;

int t,n,dp[2100];

int main()

{

    scanf("%d",&t);

    while (t--)

    {

        scanf("%d",&n);

        memset(dp,0,sizeof(dp));

        dp[0]=1;

        for (int i=2;i<=n;i++)

        {

            for (int j=i;j<=n;j++)

            {

                dp[j]=(dp[j]+dp[j-i])%mod;

            }

        }

        printf("%d\n",dp[n]);

    }

}