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++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, 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

?