CF2143D1.Inversion Graph Coloring (Easy Version)

这是本题的简单版本。不同之处在于本版本中 $n \le 300$。只有在你解决了本题所有版本后，才能进行 Hack。

一个序列 $b_1, b_2, \ldots, b_k$ 被称为“好”的，如果存在对每个下标 $i$ 的一种红色或蓝色染色方案，使得对于任意 $i < j$ 且 $b_i > b_j$ 的下标对，$i$ 和 $j$ 的颜色不同。

给定一个序列 $a_1, a_2, \ldots, a_n$。请计算该序列中“好”子序列（包括空子序列$^{\text{∗}}$）的个数。由于答案可能很大，输出它对 $10^9 + 7$ 取模的结果。

$^{\text{∗}}$ 如果序列 $b$ 可以通过从 $a$ 中删除若干（可以为零或全部）个元素得到，则称 $b$ 是 $a$ 的子序列。

每个测试点包含多组测试用例。首行为测试用例数 $t$（$1 \le t \le 100$）。接下来为每组测试用例的描述。

每组测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 300$），表示序列长度。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le n$），表示序列中的元素。

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

对于每组测试用例，输出一行，表示“好”子序列的个数，对 $10^9 + 7$ 取模。

在第一个测试用例中，不是“好”的子序列有 $[4, 3, 1]$、$[4, 2, 1]$、$[4, 2, 3, 1]$。总共有 $16$ 个子序列，因此“好”子序列有 $16 - 3 = 13$ 个。

在第三个测试用例中，所有的子序列都是“好”的。

由 ChatGPT 5 翻译