409925: GYM103855 H Beacon Towers

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.

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.

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$$$.

5
1 4 2 5 3

6

3
3 2 1

1

8
6 3 1 7 2 5 4 8

20