D1.逆序图染色（简单版本）

时间限制： 每测试 $3$ 秒
内存限制： 每测试 $512$ 兆字节

这是问题的简单版本。版本之间的区别在于，此版本中 $n \leq 300$。只有在你解决了所有版本的问题后，才能进行 hack。

一个序列 $b_1, b_2, \dots, b_k$ 被称为好的，如果存在一种将每个索引 $i$ 染成红色或蓝色的染色方案，使得对于每一对满足 $b_i > b_j$ 的索引 $i < j$，分配给 $i$ 和 $j$ 的颜色不同。

给定一个序列 $a_1, a_2, \dots, a_n$。计算该序列的好子序列的数量，包括空子序列。由于答案可能非常大，请输出其对 $10^9 + 7$ 取模的结果。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ $(1 \leq t \leq 100)$。接下来是每个测试用例的描述。

第一行包含一个整数 $n$ $(1 \leq n \leq 300)$ — 序列的长度。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ $(1 \leq a_i \leq n)$ — 序列的内容。

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

输出格式

对于每个测试用例，输出一行，包含好子序列的数量对 $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

样例解释

在第一个测试用例中，不是好的子序列有 $[4, 3, 1]$、$[4, 2, 1]$ 和 $[4, 2, 3, 1]$。由于总共有 $16$ 个子序列，这意味着有 $16 - 3 = 13$ 个好子序列。

在第三个测试用例中，每个子序列都是好的。