CF2143D2 Inversion Graph Coloring (Hard Version)

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.