Read problems statements in Russian here 
The Head Chef is interested in studying interactions between his chefs . There are  N  chefs with ids 1 to N . Each chef trusts some of the other chefs . The relation of trust is one way . Also , a chef may trust chefs only with ids strictly greater than his/her id .A chef with id = i , trusts the chefs with next n_{i} id's.  

The Head Chef wants to know given a chef B and a set of chefs S,  how many lines of trust exist between each element of S and B . A line of trust between chefs A and B is a sequence of chefs a_{1} ... a_{k} starting at A ( a_{1} = A )and finishing at B  (A_{k} = B) such that A_{i} trusts A_{(i+1) } for all i ( 1 to k-1) . Two lines of trust are different if they have a different chef at the some position in the line . 

Since the answer may be quite large , output it modulo 1000000007 .

------ Input ------ 

The first line contains a two space seperated integers N and  B denoting the number of chefs and the target chef for whom the lines of trust have to be calculated.  
The next  N lines contains an integer  n_{i} denoting the number of chefs which are trusted by the chef with id = i .  
The next line contains a single integer  Q  denoting the number of queries 
The next  Q  lines contain elements of set S .

------ Output ------ 

Output a single line for each query containing the answer to the query.

------ Constraints ------ 

$1 ≤ N ≤ 200000$
$1 ≤ B ≤ N$
$1 ≤ Q ≤ 100000$
$1 ≤ Each element of set S  < B$
$1 ≤ i + n_{i} ( for i = 1 to N )  ≤ N$
$0 ≤ n_{i} ( for i = 1 to N )  ≤ N - 1$

----- Sample Input 1 ------ 
3 3
2
1
0
2
1
2
----- Sample Output 1 ------ 
2
1
----- explanation 1 ------ 
Example case 1. The lines of trust between 1 and 3 are 
1 , 3 
1 , 2 ,3 
There is one line of trust between 2 and 3 which is 
2 3

Source: codechef | Difficulty: HARD
Tags: Graph algorithms

Directed graphs

Range queries

Segment trees revisited

Dynamic programming

Data structures


Solutions:
(n, b) = [int(x) for x in input().split()]
ni = [0 for _ in range(n + 1)]
for i in range(1, n + 1):
	ni[i] = int(input())
dp = [0 for _ in range(b + 1)]
cum = [0 for _ in range(n + 2)]
dp[b - 1] = 1
dp[b] = 0
cum[b] = 1
cum[b - 1] = 2
md = int(1000000000.0 + 7)
for i in range(b - 2, 0, -1):
	dp[i] = (cum[i + 1] - cum[i + ni[i] + 1] + md) % md
	cum[i] = (dp[i] + cum[i + 1]) % md
q = int(input())
for i in range(q):
	qu = int(input())
	print(dp[qu])