Out of Control

Problem Description

There is a cloud service API to help user store history timestamps. The data structure for each user is initially an empty stack. Every time you post a request to the API with an integer $x$, denoting the current timestamp, the service will append $x$ to the end of the stack. When $x$ is less than the previous timestamp stored in the stack, the service will think the input is wrong, and will append the previous timestamp instead of $x$. You have posted the API for $n$ times, your request timestamp is $x_i$ in the $i$-th call. However, the network is out of control. The service may receive your requests in any arbitrary order, and may even miss some requests. Knowing this issue, you are asking for the on-call engineer to have a look at your stack in the database. Assume the service received exactly $k$ requests, how many possible distinct stacks will it be?

Input

The first line contains a single integer $T$ ($1 \leq T \leq 100$), the number of test cases. For each test case: The first line of the input contains a single integer $n$ ($1 \leq n \leq 3\,000$), denoting the total number of requests. The second line contains $n$ integers $x_1,x_2,\dots,x_n$ ($1\leq x_i\leq 10^9$), denoting the timestamp of each request. It is guaranteed that the sum of all $n$ is at most $30\,000$.

Output

For each test case, output $n$ lines, the $i$-th ($1\leq i\leq n$) of which containing an integer, denoting the number of distinct stacks when $k=i$. Note that the answer may be extremely large, so please print it modulo $10^9+7$ instead.

Sample Input

2
3
1 2 3
3
2 3 3

Sample Output

3
5
5
2
2
2

Hint

In the first example:

• When $k=1$, the stack can be $[1]$, $[2]$ or $[3]$.
• When $k=2$, the stack can be $[1,2]$, $[1,3]$, $[2,2]$, $[2,3]$ or $[3,3]$.
• When $k=3$, the stack can be $[1,2,3]$, $[1,3,3]$, $[2,2,3]$, $[2,3,3]$ or $[3,3,3]$. In the second example:
• When $k=1$, the stack can be $[2]$ or $[3]$.
• When $k=2$, the stack can be $[2,3]$ or $[3,3]$.
• When $k=3$, the stack can be $[2,3,3]$ or $[3,3,3]$.

Source

2023“钉耙编程”中国大学生算法设计超级联赛（3）