This is the hard version of the problem. The difference between the versions is that in this version, $$$n \le 2000$$$. 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 2000$$$) — 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 $$$2000$$$.

Output

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

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.

Inversion Graph Coloring (Hard Version)

Examples