D2. Inversion Graph Coloring (Hard Version)time limit per test3 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output 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 < j$$$ with $$$b_i > 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. InputEach 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 sequenceThe 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$$$. OutputFor each test case, output a single line containing the number of good subsequences modulo $$$10^9 + 7$$$.ExampleInput444 2 3 177 6 1 2 3 3 251 1 1 1 1117 2 1 9 7 3 4 1 3 5 3Output137332619NoteIn 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.