Too Many LIS 2

 This problem has two subtasks worth 

50$50$ points each.

You are given an integer N$N$. You also have N$N$ empty sets S1,S2,…,SN$S_1,S_2,\dots ,S_N$.

Consider all the arrays A$A$ of length N$N$ such that 0≤Ai≤1$0\le A_i\le 1$ for each 1≤i≤N$1\le i\le N$ (there are 2N$2^N$ such arrays in total).

For each of these 2N$2^N$ arrays, we compute an array B$B$ of length N$N$ where Bi=$B_i=$ length of longest non-decreasing subsequence for the prefix of length i$i$ of array A$A$. (For example: if N=5$N=5$ and A=[0,1,0,1,1]$A=[0,1,0,1,1]$, then B=[1,2,2,3,4]$B=[1,2,2,3,4]$.) Next we add the array B$B$ to the set SBN$S_{B_N}$ (For example, B=[1,2,2,3,4]$B=[1,2,2,3,4]$ would be added to S4$S_4$).

Output the size of sets S1,S2,…,SN$S_1,S_2,\dots ,S_N$ as N$N$ space-separated integers. Since the size of the sets might be large, output the values modulo 109+7${10}^9+7$.

Note that the Si$S_i$ are sets, and hence do not contain duplicate elements. Please look at the sample cases below for an explained example.

Input Format

• The first line of input will contain a single integer T$T$, denoting the number of test cases. The description of T$T$ test cases follows.
• The first and only line of each test case contains a single integer N$N$.

Output Format

For each test case, output on a new line the N$N$ space separated integers, size of sets S1,S2,…,SN$S_1,S_2,\dots ,S_N$, modulo 109+7${10}^9+7$.

Constraints

• 1≤T≤500$1\le T\le 500$
• 1≤N≤2⋅105$1\le N\le 2\cdot {10}^5$
• The sum of N$N$ over all tests won't exceed 2⋅105$2\cdot {10}^5$.

Subtasks

Subtask #1 (50 points):

• 1≤T≤100$1\le T\le 100$
• 1≤N≤5⋅103$1\le N\le 5\cdot {10}^3$
• The sum of N$N$ over all tests won't exceed 5⋅103$5\cdot {10}^3$.

Subtask #2 (50 points): Original constraints

Sample Input 1 

3
2
3
4

Sample Output 1 

1 1
0 2 1
0 2 3 1

Explanation

Test case 1$1$:

• For A=[0,0]$A=[0,0]$, B=[1,2]$B=[1,2]$
• For A=[0,1]$A=[0,1]$, B=[1,2]$B=[1,2]$
• For A=[1,0]$A=[1,0]$, B=[1,1]$B=[1,1]$
• For A=[1,1]$A=[1,1]$, B=[1,2]$B=[1,2]$

Therefore, S1={[1,1]},S2={[1,2]}$S_1=\{[1,1]\},S_2=\{[1,2]\}$

Test case 2$2$:

• For A=[0,0,0]$A=[0,0,0]$, B=[1,2,3]$B=[1,2,3]$
• For A=[0,0,1]$A=[0,0,1]$, B=[1,2,3]$B=[1,2,3]$
• For A=[0,1,0]$A=[0,1,0]$, B=[1,2,2]$B=[1,2,2]$
• For A=[0,1,1]$A=[0,1,1]$, B=[1,2,3]$B=[1,2,3]$
• For A=[1,0,0]$A=[1,0,0]$, B=[1,1,2]$B=[1,1,2]$
• For A=[1,0,1]$A=[1,0,1]$, B=[1,1,2]$B=[1,1,2]$
• For A=[1,1,0]$A=[1,1,0]$, B=[1,2,2]$B=[1,2,2]$
• For A=[1,1,1]$A=[1,1,1]$, B=[1,2,3]$B=[1,2,3]$

Therefore, S1={},S2={[1,1,2],[1,2,2]},S3={[1,2,3]}$S_1=\{\},S_2=\{[1,1,2],[1,2,2]\},S_3=\{[1,2,3]\}$

Test case 3$3$: S1={},S2={[1,1,2,2],[1,2,2,2]},S3={[1,1,2,3],[1,2,2,3],[1,2,3,3]},S4={[1,2,3,4]}