Number of Paths

All submissions for this problem are available.
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 k1) . 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
Example
Input: 3 3 2 1 0 2 1 2 Output: 2 1
Explanation
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
Author:  vineetpaliwal 
Editorial  http://discuss.codechef.com/problems/NUMPATH 
Tags  cook40 dynamicprogramming fenwick medium vineetpaliwal 
Date Added:  28102013 
Time Limit:  0.5 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.4, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 