409925: GYM103855 H Beacon Towers

Memory Limit:1024 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

H. Beacon Towerstime limit per test1 secondmemory limit per test1024 megabytesinputstandard inputoutputstandard output

There are $$$N$$$ villages in a row, numbered from $$$1$$$ to $$$N$$$. Village $$$1$$$ is the leftmost village and village $$$N$$$ is the rightmost village. The heights of the villages are distinct integers ranging from $$$1$$$ to $$$N$$$.

You would like to divide the villages into several segments. Each segment must contain at least one village and every village should belong to exactly one segment. If two villages are in the same segment, then all villages in between them must also be in that segment.

In each segment, a beacon will be installed in the village with the highest height. For efficient mutual communication among beacon towers, the heights of the villages where the beacon towers are installed must form an increasing sequence from left to right.

Please count the number of possible segment divisions that will cause the beacon towers to satisfy the given constraints.

Input

The first line contains an integer $$$N$$$ representing the number of villages ($$$1 \leq N \leq 500\,000$$$). The second line contains $$$N$$$ integers $$$h_1, h_2, \cdots, h_N$$$ representing the heights of villages $$$1, 2, \ldots, N$$$. ($$$1 \leq h_i \leq N$$$). All $$$h_i$$$'s are distinct.

Output

Count the number of possible segment divisions that will cause the beacon towers to satisfy the given constraints. As the answer could be large, please output the answer modulo $$$10^9 + 7$$$.

ExamplesInput
5
1 4 2 5 3
Output
6
Input
3
3 2 1
Output
1
Input
8
6 3 1 7 2 5 4 8
Output
20

加入题单

上一题 下一题 算法标签: