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$ 中有两个或更多点，那么可以通过以下两种方式之一对它执行编排操作，得到一个由 $s$ 中所有点各出现一次组成的序列： - 任选一个整数 $x$，将 $s$ 分成两部分：$X$ 坐标小于 $x$ 的点组成集合 $a$，其余点组成集合 $b$。要求 $a$ 和 $b$ 都非空。先对 $a$ 执行编排操作，再对 $b$ 执行编排操作，然后将 $a$ 得到的序列和 $b$ 得到的序列按 $a$ 在前、$b$ 在后的顺序拼接起来，形成一个序列。 - 任选一个整数 $y$，将 $s$ 分成两部分：$Y$ 坐标小于 $y$ 的点组成集合 $a$，其余点组成集合 $b$。要求 $a$ 和 $b$ 都非空。先对 $a$ 执行编排操作，再对 $b$ 执行编排操作，然后将 $a$ 得到的序列和 $b$ 得到的序列按 $a$ 在前、$b$ 在后的顺序拼接起来，形成一个序列。 求对点集 $\{(1,P_1),(2,P_2),\cdots,(N,P_N)\}$ 执行编排操作所能得到的不同序列的个数，对 $10^9+7$ 取模。

输入按以下格式从标准输入给出： > $N$ > > $P_1$ $P_2$ $\cdots$ $P_N$

一行一个整数，表示答案。

### 限制 - $1 \leq N \leq 30$ - $(P_1,P_2,\cdots,P_N)$ 是 $(1,2,\cdots,N)$ 的一个排列。 - 输入中的所有值均为整数。 ### 样例解释 1 可以得到以下三个序列。 - $((1,3),(2,1),(3,2))$ - $((2,1),(3,2),(1,3))$ - $((2,1),(1,3),(3,2))$ 例如，序列 $((2,1),(1,3),(3,2))$ 可以按如下方式得到。 - 对点集 $\{(1,3),(2,1),(3,2)\}$ 执行编排操作，将其分成 $Y$ 坐标小于 $2$ 的点集（即 $\{(2,1)\}$）和其余点集（即 $\{(1,3),(3,2)\}$）。 - 对点集 $\{(2,1)\}$ 执行编排操作，得到序列 $((2,1))$。 - 对点集 $\{(1,3),(3,2)\}$ 执行编排操作，将其分成 $X$ 坐标小于 $3$ 的点集和其余点集。 - 对点集 $\{(1,3)\}$ 执行编排操作，得到序列 $((1,3))$。 - 对点集 $\{(3,2)\}$ 执行编排操作，得到序列 $((3,2))$。 - 将得到的两个序列拼接起来，得到序列 $((1,3),(3,2))$。 - 将得到的两个序列拼接起来，得到序列 $((2,1),(1,3),(3,2))$。