题目描述

这是该题的困难版本（Hard 版）。不同版本的区别在于本版本中 $n\le 2000$。

序列 $b_1,b_2,\dots,b_k$ 被称为 good（良好）的，当且仅当存在对每个下标 $i$ 进行红/蓝着色的方式，使得对任意满足 $i<j$ 且 $b_i>b_j$ 的一对下标 $i,j$，它们的颜色恰好不同。

现在给定序列 $a_1,a_2,\dots,a_n$，请计算序列的 good 子序列的个数（包括空子序列）。由于答案可能非常大，请对 $10^9+7$ 取模后输出答案。

说明：序列 $b$ 是序列 $a$ 的子序列，当且仅当 $b$ 可以通过删除序列 $a$ 的若干（可能为 $0$ 或全部）元素并保持相对顺序得到。

输入格式

第一行包含一个整数 $t$，表示测试用例的数量（$1\le t\le 100$）。

每个测试用例包含两行：

• 第一行包含整数 $n$，表示序列长度（$1\le n\le 2000$）。
• 第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$（$1\le a_i\le n$）。

保证所有测试用例中 $n$ 的总和不超过 $2000$。

输出格式

对于每个测试用例，输出一行，包含一个整数：序列的 good 子序列个数（对 $10^9+7$ 取模）。

样例输入

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

样例输出

13
73
32
619

说明

样例解释

• 在第一个样例中，不是 good 的子序列有 $[4,3,1]$、$[4,2,1]$ 和 $[4,2,3,1]$，总共有 $2^4=16$ 个子序列，因此答案为 $16-3=13$。
• 在第三个样例中，由于所有元素相等，任意子序列都是 good。