All Tracks Algorithms Dynamic Programming Problem

Trystland rulers
Tag(s):

Easy-Medium

Problem
Editorial
Analytics

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$$

SAMPLE INPUT
2
1 2
SAMPLE OUTPUT
2
Explanation

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]

Time Limit: 0.5 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Scala 2.11.8, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

IIT Delhi

Challenge Name

ICPC de Tryst

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications