SOLVE
LATER
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$$
Possible final configurations:
1 1 [If the ruler of first city decides to capture 1 city]
1 2 [If the ruler of first city decides to capture 0 cities]