There is a kingdom, Trystland with n cities aligned in a row. Each city i is ruled by some ruler \(R_i\).

Now, starting from city 1 to n, the ruler of the city decides how many cities to the right he wants to capture. In other words, say ruler of city i decides to capture k cities, \(0 \le k \le n-i\), then the ruler of all the cities j, where \(i \le j \le i+k\), gets immediately changed to the ruler of city i.

You are required to find number of different configurations that are possible after the decisions of all the rulers. As the number could be quite large, print the answer modulo \(10^9 + 7\)

Input

The first line consists of an integer n denoting number of cities in the kingdom.

The second line consists of n space seperated integers denoting the sequence of rulers of cities. \(i^{th}\) integer indicate the ruler of the \(i^{th}\) city.

Output

Print one line containing the number of possible configurations modulo \(10^9 + 7\).

Constraints

• \(1 \le n \le 100000\)

• \( 1 \le R_i \le 100\)