4350: 不是唯一的树

我们都知道，要构建传统的“二叉搜索树”，我们将较小的数字放在左侧，而较大的数字放在右侧。不同的数据顺序可能会导致不同的树结构。

在这个问题中，您需要计算有多少个不同的输入序列才能获得具有特定结构的二叉搜索树。

第一行一个整数 t（1 <= t <= 100） 代表测试用例组数。每组测试用例包含两行：

第一行是整数 n。

第二行是 [1， n] 的排列，描述根据序列顺序构造的二叉搜索树。

1 ≤ n ≤ 10³.

对于每个测试用例，输出可以构建具有相同结构的二叉搜索树的不同序列的数量，包括输入序列。

结果应为模数10⁹+ 7.

2
4
3 2 4 1
5
3 5 2 1 4

3
6