题目描述

给定一个长为 $n$ 的点列 $(i,p_i)$，其中 $\{p_i\}$ 是一个 $1$ 到 $n$ 的排列。

每次操作可以选择 $x/y$ 和一个坐标，将点列分成左右/上下两边（保持两边的相对顺序不变），分别递归下去，直到只剩下一个点，把它加入答案序列末尾。

求最终能生成多少种不同的答案序列，对 $10^9+7$ 取模。

输入格式

第一行一个正整数 $n$，表示点列长度。

第二行一个长为 $n$ 的排列 $p_i$。

输出格式

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

输入输出样例 #1

输入 #1

3
3 1 2

输出 #1

3

输入输出样例 #2

输入 #2

5
1 2 3 4 5

输出 #2

1

输入输出样例 #3

输入 #3

10
3 6 4 8 7 2 10 5 9 1

输出 #3

1332

输入输出样例 #4

输入 #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

说明/提示

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