题目描述

一条海岸（直）线上有 \(n\) 个村庄，最左边的村庄标号为 \(1\)，最右边的村庄标号为 \(n\)。每座村庄有一座高度在 \([1,n]\) 的信号塔。由于城市改造，我们需要把 \(n\) 个村庄分成若干连续区间，要求每个部分至少存在一座村庄并且每个村庄都要在一个区间里面（如果村庄 \(i\) 和村庄 \(j\) 在一个区间里，说明 \(i+1, i+2, ⋯ , j−1, j\) 也在一个区间里)。

我们在每个区间里都要点亮区间中最高的信号塔，由于一些特殊的原因，从左到右点亮的信号塔高度需要是递增的。

Smart 想知道有多少种村庄的划分方法使得能点亮每个区间的信号塔呢？由于划分方法可能很大，Smart 希望你把答案对 \(10^9+7\) 取模。

格式

输入格式

第一行一个数 \(n\),表示村庄的数量。

第二行 \(n\) 个数 \(h_i\)。表示第 \(i\) 座村庄信号塔的高度。保证 \(h_i\) 互不相同。

输出格式

一个数表示答案。

样例1

样例输入1

5
1 4 2 5 3

样例输出1

6

限制

对于 \(30\%\) 的数据，\(1≤n≤5\)；

对于 \(60\%\) 的数据，\(1≤n≤3000\)；

对于 \(100\%\) 的数据，\(1≤n≤500000,1≤h_i≤n\)；

来源

地址：\(zloj,J2020\)域
作者：\(jialiang2509\)