나무 품종 세기

친구 Darwin은 매우 유명한 박물학자입니다. 그는 2년 전에 발견한 특정 종의 나무가 몇 가지 품종인지 세고 있다고 말합니다.

이 나무에는 특이한 점이 있습니다. 첫째, 나무는 납작해서 한쪽 면은 남쪽을, 다른 면은 북쪽을 향합니다. 둘째, 가지가 갈라질 때는 정확히 두 개의 하위 가지로 나뉘며, 하나는 서쪽으로, 다른 하나는 동쪽으로 뻗습니다. 따라서 이 나무는 컴퓨터 과학자에게 익숙한 이진 트리로 쉽게 나타낼 수 있습니다. (수학적으로 이진 트리는 빈 트리이거나, 두 자식이 각각 이진 트리인 내부 노드 하나입니다.)

Darwin은 가지가 수평이거나 위로 뻗는다고 설명합니다. 이진 트리 표현에서 각 내부 노드에 가지가 갈라지는 높이(지면으로부터의 거리)를 적으면, 루트가 아닌 노드의 값은 항상 부모의 값보다 크거나 같습니다. 빈 트리에는 값이 없습니다.

이 종의 나무라면 어떤 나무든 값이 붙은 이진 트리의 중위 순회로 얻는 높이 수열이 항상 같습니다. (빈 트리의 중위 순회는 빈 수열입니다. 빈 트리가 아니면 왼쪽 부분 트리의 중위 순회, 루트의 값, 오른쪽 부분 트리의 중위 순회를 차례로 이어 붙인 수열입니다.)

Darwin의 가설은 품종마다 같은 이진 트리가 대응하며, 그 이진 트리가 품종을 하나로 정한다는 것입니다. 또한 위 조건을 만족하는 값 붙은 이진 트리는 모두 실제로 존재하는 품종에 대응합니다. Darwin은 수학적 도구로 품종 수를 셀 수 있다고 믿지만, 그 방법은 알지 못합니다.

이 종의 품종 수를 세는 프로그램을 작성하세요.

첫 줄에 이 종의 나무 하나를 중위 순회해서 얻은 높이 수열의 원소 개수 N이 주어집니다.

이어지는 N개의 줄에는 높이(밀리미터)를 나타내는 정수가 한 줄에 하나씩 주어집니다.

이 종의 품종 수를 1 000 000 007로 나눈 나머지를 한 줄에 출력합니다.

N과 높이는 모두 0 이상 1 000 000 이하입니다.