봉화대

문제

$N$개의 마을이 일렬로 1번부터 $N$번까지 순서대로 산등성이를 따라 있다. 각 마을의 높이는 1 이상 $N$ 이하의 자연수 중 하나이며 서로 다르다. 외침을 막기 위해 마을을 여러 구간으로 나누어, 각 구간의 가장 높은 마을에 봉화대를 설치하려 한다. 각 구간은 하나 이상의 연속된 마을을 포함해야 하고, 각 마을은 정확히 하나의 구간에 포함되어야 한다. 봉화대의 효율적인 상호 통신을 위해, 봉화대가 설치된 마을의 높이는 번호의 오름차순으로 봤을 때 증가해야 한다. 전략 도모를 위해 가능한 구간 배치의 개수를 파악해보고자 한다.

그림 H.1: 조건을 만족한 봉화대 설치 예시	그림 H.2: 조건을 만족하지 않은 봉화대 설치 예시

입력

첫째 줄에는 마을의 개수를 의미하는 정수 $N$이 주어진다. ($1\le N\le 500000$)

둘째 줄에는 각 마을의 높이를 의미하는 $N$개의 정수 $h_1,h_2,\cdots ,h_N$이 공백으로 구분되어 주어진다. ($1\le h_i\le N$)

$h_i$는 $i$번째 마을의 높이를 의미하며 서로 다르다.

출력

조건을 만족하며 $N$개의 마을을 구간으로 나누는 방법의 가짓수를 $1000000007$로 나눈 나머지를 출력한다.

힌트

첫 번째 예제의 가능한 모든 배치는 (1 / 4 / 2 5 3),  (1 / 4 2 / 5 3), (1 / 4 2  5 3), (1 4 / 2 5 3), (1 4 2 /  5 3), (1 4 2 5 3) 이다. /는 구간의 경계이며, 봉화대는 밑줄로 강조된 높이의 마을에 설치된다.

예제 입력 1 복사

5
1 4 2 5 3

예제 입력 2 복사

3
3 2 1

예제 입력 3 복사

8
6 3 1 7 2 5 4 8

예제 출력 1 복사

6

예제 출력 2 복사

1

예제 출력 3 복사

20