问题描述

平面上有N个点，其中第i个点（$1 \leq i \leq N$）的坐标为$(i,P_i)$。这里，$(P_1,P_2,\cdots,P_N)$是$(1,2,\cdots,N)$的一个排列。

你可以排列一个非空点集$s$，该操作定义如下。

• 如果$s$只包含一个点，那么排列它将得到由该点组成的序列。
• 如果$s$包含两个或更多个点，那么排列它将通过以下两种操作之一得到由这些点组成的序列：
  • 选择任意整数$x$并将$s$分成两部分：坐标的$X$值小于$x$的点构成的集合$a$和其余点构成的集合$b$。这里，$a$和$b$都不能为空。通过连接排列$a$得到的序列和排列$b$得到的序列得到一个序列。
  • 选择任意整数$y$并将$s$分成两部分：坐标的$Y$值小于$y$的点构成的集合$a$和其余点构成的集合$b$。这里，$a$和$b$都不能为空。通过连接排列$a$得到的序列和排列$b$得到的序列得到一个序列。

求按照点集$\\{(1,P_1),(2,P_2),\cdots,(N,P_N)\\}$的排列方式，模$(10^9+7)$的结果。

约束条件

• $1 \leq N \leq 30$
• $(P_1,P_2,\cdots,P_N)$是$(1,2,\cdots,N)$的一个排列。
• 输入中的所有值都是整数。

输入

输入以标准格式给出，格式如下：

$N$ $P_1$ $P_2$ $\cdots$ $P_N$

输出

输出答案。

示例输入1

3
3 1 2

示例输出1

3

可以得到以下三个序列。

• $((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))$。

示例输入2

5
1 2 3 4 5

示例输出2

1

示例输入3

10
3 6 4 8 7 2 10 5 9 1

示例输出3

1332

示例输入4

30
7 11 8 26 4 13 28 5 14 1 16 27 10 2 23 25 17 6 3 18 24 15 9 22 21 29 12 20 19 30

示例输出4

641915679