Split the GSHS 2

Interview

Time limit1sMemory limit1024 MB

Summary

Count the ways to split students 1 to N into consecutive groups, where each group's size is an endpoint leader's A plus 1, modulo 1e9+7.

Level: Medium5 of 10
Topics: Dynamic programming, Array
Solved: No attempts yet

Problem

Gyeonggi Science High School, a landmark of Gyeonggi-do, has $N$ students. The villain Donghyun plans to divide the students of Gyeonggi Science High School and then take control of the school. The first part of his plan is to weaken the school by splitting its students into several groups. Donghyun intends to form the groups according to the following rules.

Each student has a unique leadership value $A_i$ . A student with leadership $A_i$ can be the leader of a group that contains exactly $A_i$ members other than themselves. In other words, the size of a group led by the student with leadership $A_i$ must be exactly $A_i+1$ , including the leader.
Every student must belong to exactly one group. No student may belong to no group or to two or more groups.
Every group must consist of students with consecutive numbers. That is, the student numbers in a group must have the form $\{s,s+1,\cdots ,e\}$ for some $1\leq s\leq e\leq N$ .
For the group to be represented fairly, the leader must be either the student with the smallest number or the student with the largest number. That is, in a group whose student numbers form $\{s,s+1,\cdots ,e\}$ , the leader is student $s$ or student $e$ .

The problem is that there are a very large number of ways to split the groups. Donghyun asks you to count the ways to split the students. Write a program that computes this number for him.

Input

The first line contains the number of students $N$ at Gyeonggi Science High School.

The second line contains $N$ integers $A_1$ , $A_2$ , $\cdots$ , $A_N$ , separated by spaces, which represent the leadership of each student.

Output

Print, on the first line, the number of ways to split the students according to the rules above, modulo $10^9+7$ .

Constraints

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

Examples3

Example 1
Input
```
7
4 2 2 3 1 1 3
```
Expected output
```
3
```
Example 2
Input
```
5
1 1 1 1 1
```
Expected output
```
0
```
Example 3
Input
```
4
1 1 1 1
```
Expected output
```
1
```