D1. Inversion Graph Coloring (Easy Version)
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

This is the easy version of the problem. The difference between the versions is that in this version, $$$n \le 300$$$. You can hack only if you solved all versions of this problem.

A sequence $$$b_1, b_2, \ldots, b_k$$$ is called good if there exists a coloring of each index $$$i$$$ in red or blue such that for every pair of indices $$$i \lt j$$$ with $$$b_i \gt b_j$$$, the colors assigned to $$$i$$$ and $$$j$$$ are different.

You are given a sequence $$$a_1, a_2, \ldots, a_n$$$. Compute the number of good subsequences of the sequence, including the empty subsequence$$$^{\text{∗}}$$$. Since the answer can be very large, output it modulo $$$10^9 + 7$$$.

$$$^{\text{∗}}$$$A sequence $$$b$$$ is a subsequence of a sequence $$$a$$$ if $$$b$$$ can be obtained from $$$a$$$ by the deletion of several (possibly, zero or all) element from arbitrary positions.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 100$$$). The description of the test cases follows.

The first line contains an integer $$$n$$$ ($$$1 \leq n \leq 300$$$) — the length of the sequence

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — the contents of the sequence.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$300$$$.

Output

For each test case, output a single line containing the number of good subsequences modulo $$$10^9 + 7$$$.

Example
Input
4
4
4 2 3 1
7
7 6 1 2 3 3 2
5
1 1 1 1 1
11
7 2 1 9 7 3 4 1 3 5 3
Output
13
73
32
619
Note

In the first test case, the subsequences that are not good are $$$[4, 3, 1]$$$, $$$[4, 2, 1]$$$, and $$$[4, 2, 3, 1]$$$. Since there are $$$16$$$ subsequences in total, this means there are $$$16 - 3 = 13$$$ good subsequences.

In the third test case, every subsequence is good.