题目描述

平面上有 $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$ 取模的结果。

样例 1

输入

3
3 1 2

输出

3

样例 2

输入

5
1 2 3 4 5

输出

1

样例 3

输入

10
3 6 4 8 7 2 10 5 9 1

输出

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

输出

641915679

说明/提示

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