ULTIMATE STAIRWAY TO HEAVEN!

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. 

Example:

Input: n=8, nums = { 3, 1, 0, 1, 3, 3, 0, 1 }
Output: 2

Approach

Java

public class ULTIMATETOHEAVEN {
    private static final int MOD = 1000000007;

    public static void main(String[] args) {
        int n = 8;

        int[] nums = { 3, 1, 0, 1, 3, 3, 0, 1 };
        long[] range = new long[n + 2];

        if (nums[0] > 0) {
            range[1] = 1;
        }

        if (nums[0] + 1 < n) {
            range[nums[0] + 1] -= 1;
        }

        long overlap = 0;

        for (int i = 1; i < n; i++) {
            int r = nums[i];

            overlap = (range[i] % MOD + overlap % MOD) % MOD;

            if (i + 1 < n) {
                range[i + 1] = ((range[i + 1] % MOD) + (overlap % MOD)) % MOD;
            }

            if (i + r + 1 <= n) {
                range[i + r + 1] = (MOD + range[i + r + 1] - overlap);
            }
        }

        System.out.println(overlap);
    }

}