31748번 - Split the 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)$

서브태스크

힌트