히스토그램 연결 경우의 수

2차원 격자는 양의 정수 쌍의 집합으로 나타낼 수 있다. 각 칸은 아래 그림과 같이 번호를 붙일 수 있다.

각 열의 높이가 $h_1, h_2, \cdots, h_N$인 히스토그램이 주어진다. 이 히스토그램의 영역은 $i = 1, 2, \cdots, N$에 대해 칸 $(i, 1), (i, 2), \cdots, (i, h_i)$를 모두 포함하는 집합으로 나타낼 수 있다. ($h_i = 0$이면 $i$번째 열에는 칸이 하나도 없다는 뜻이다.)

$0 \le x_i < h_i$인 $N$개의 정수 $x_1, x_2, \cdots, x_N$을 골라 높이가 $x_1, x_2, \cdots, x_N$인 부분 히스토그램을 빼낼 수 있다. 이렇게 부분 히스토그램을 제거하고 남은 영역은 다음과 같다. $\bigcup_{i=1}^N \{ (i, j) : x_i < j \le h_i \}.$

예를 들어 아래 그림은 $h_1 = 4$, $h_2 = 5$, $h_3 = 4$, $h_4 = 4$이고 $x_1 = 1$, $x_2 = 2$, $x_3 = 3$, $x_4 = 2$인 경우를 나타낸다.

남은 영역이 연결되어 있다는 것은, 남은 영역에 속한 모든 칸 쌍 $((r_1, c_1), (r_2, c_2))$에 대해 다음 이동만으로 남은 영역을 벗어나지 않고 $(r_1, c_1)$에서 $(r_2, c_2)$로 갈 수 있다는 뜻이다.

• $(r, c) \to (r+1, c)$
• $(r, c) \to (r-1, c)$
• $(r, c) \to (r, c+1)$
• $(r, c) \to (r, c-1)$

남은 영역이 연결되도록 하는 $(x_1, x_2, \cdots, x_N)$의 경우의 수를 구하여라.

첫째 줄에 정수 $N$이 주어진다. 둘째 줄에 $N$개의 정수 $h_1, h_2, \cdots, h_N$이 순서대로 주어진다.

남은 영역이 연결되도록 하는 $(x_1, x_2, \cdots, x_N)$의 경우의 수를 $10^9 + 7$로 나눈 나머지를 출력한다.

• $1 \le N \le 250\,000$
• $1 \le h_i \le 10^9$