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. 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). For each test case, output a single line containing the number of good subsequences modulo (10^9 + 7). 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.