AT_arc138_f [ARC138F] KD Tree

平面上有 $N$ 个点，其中第 $i$ 个点 $(1 \le i \le N)$ 的坐标为 $(i, P_i)$。 这里，$(P_1, P_2, \cdots, P_N)$ 是 $(1, 2, \cdots, N)$ 的一个排列。 你可以对一个非空点集 $s$ 进行“排列”，这是一个递归定义的操作： - 若 $s$ 恰好包含一个点，则排列它得到仅由该点组成的序列。 - 若 $s$ 包含两个或更多点，则通过以下两种操作之一来排列它，从而得到由这些点组成的序列： - 选择任意整数 $x$，将 $s$ 划分为两个子集：$a$ 是 $x$ 坐标小于 $x$ 的点构成的集合，$b$ 是其余点构成的集合。这里，$a$ 和 $b$ 都不能为空。将排列 $a$ 得到的序列与排列 $b$ 得到的序列按顺序拼接，得到一个新序列。 - 选择任意整数 $y$，将 $s$ 划分为两个子集：$a$ 是 $y$ 坐标小于 $y$ 的点构成的集合，$b$ 是其余点构成的集合。这里，$a$ 和 $b$ 都不能为空。将排列 $a$ 得到的序列与排列 $b$ 得到的序列按顺序拼接，得到一个新序列。 求通过对点集 $\{(1, P_1), (2, P_2), \cdots, (N, P_N)\}$ 进行排列所能得到的不同序列的数量，答案对 $10^9 + 7$ 取模。

第一行一个正整数 $n$，表示点列长度。 第二行一个长为 $n$ 的排列 $p_i$。

一行一个整数，表示答案序列数量对 $10^9+7$ 取模的结果。

对于所有数据，$n\le 30$，保证 $p_i$ 是一个 $1$ 到 $n$ 的排列。