GSHS 분할 2

경기도의 명소인 경기과학고등학교에는 $N$명의 학생이 있습니다. 악당 동현이는 경기과학고등학교의 학생들을 분열시킨 뒤 학교를 지배할 계획을 세우고 있습니다. 동현이가 고안한 첫 번째 계획은 학생들을 여러 그룹으로 나누어 학교를 약화시키는 것입니다. 동현이는 다음 규칙에 따라 학생들을 그룹화하려고 합니다.

• 학생마다 고유한 리더십 $A_i$가 있습니다. 리더십이 $A_i$인 학생은 자신을 제외하고 정확히 $A_i$명의 조원을 포함한 그룹의 리더가 될 수 있습니다. 즉, 리더십이 $A_i$인 학생이 리더인 그룹의 크기는 본인을 포함해서 정확히 $A_i+1$이어야 합니다.
• 모든 학생은 정확히 하나의 그룹에 속해야 합니다. 어떤 학생도 속한 그룹이 없거나 두 개 이상이면 안 됩니다.
• 모든 그룹은 연속된 번호를 가진 학생들로 이루어져야 합니다. 즉, 한 그룹에 속한 학생들의 번호는 어떤 두 수 $1\leq s\leq e\leq N$에 대해 $\{s,s+1,\cdots ,e\}$와 같은 꼴만 가능합니다.
• 그룹의 대표성을 위해 번호가 가장 작은 학생이나 가장 큰 학생이 리더여야 합니다. 즉, 학생 번호의 집합이 $\{s,s+1,\cdots ,e\}$인 그룹에서 리더는 $s$번 학생 또는 $e$번 학생입니다.

문제는 그룹을 나누는 방법의 수가 매우 많다는 것입니다. 동현이는 당신에게 그룹을 나누는 방법의 수를 알려 달라고 요청했습니다. 동현이를 위해 그 방법의 수를 구하는 프로그램을 작성해 주세요.

첫째 줄에 경기과학고등학교에 재학 중인 학생의 수 $N$이 주어집니다.

둘째 줄에 각 학생의 리더십을 나타내는 $N$개의 정수 $A_1$, $A_2$, $\cdots$, $A_N$이 공백으로 구분되어 주어집니다.

첫째 줄에 위 규칙에 맞게 학생을 나누는 방법의 수를 $10^9+7$로 나눈 나머지를 출력합니다.

• $2\le N\le 10^5$
• $1\le A_i\le N$ $(1\le i\le N)$