All Tracks Algorithms Dynamic Programming Introduction to Dynamic Programming 1 Problem

ULTIMATE STAIRWAY TO HEAVEN!
/

Dynamic Programming

Problem
Editorial
Analytics

Debapratim likes Monali and asked her out on a date. She agreed but on a condition that he must reach the top of the Ultimate Stairway to Heaven.

The stairway consists of N stairs. Initially, Debapratim is standing on the 1st stair. The kth stair is associated with a number Ak such that, for 0 < i < Ak, Debapratim can jump to the (k+i)th stair from the kth stair.

Your task is to find the no. of ways in which Debapratim can reach the Nth stair, the top of the Ultimate Stairway to Heaven. Since the answer can be large, compute it modulo 1000000007.

All test cases are designed such that every stair of the Ultimate Stairway to Heaven is reachable in at least one way

Input:

The first line contains a single integer N.

Next line contains N space separated integers Ak , 0 < k < N.

 

Output:

Print a single line containing one integer, the no. of ways in which Debapratim can reach the Nth stair modulo 1000000007.

 

Constraints:

1 < N < 105

0 < Ak < N

 

 

SAMPLE INPUT
8
3 1 0 1 3 3 0 1
SAMPLE OUTPUT
2
Explanation

Debapratim starts from the 1st stair.

1st way: 1 -> 4 -> 5 -> 8

2nd way: 1-> 4 -> 5-> 6-> 8

It can be easily verified that there are no other ways!

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems

Contributors

Initializing Code Editor...
Notifications
View All Notifications

?