Number of Paths

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₁ ... a_k starting at A ( a₁ = 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

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 

----------------------------------------------------------------------EDITORIAL-----------------------------------------------------------

DIFFICULTY:

Medium

PREREQUISITES:

Dynamic Programming, Suffix Sum, Fenwick Tree

PROBLEM:

Given a Directed-Acyclic-Graph (DAG) G = (V, E) in which node i has edges to nodes in [i + 1, i + N[i]], find how many paths are there between S[i] and T.

EXPLANATION:

This DAG is really special and the order of 1 ... V is exactly same as its topo order in which edges are only existed from previous nodes to their later ones.

Use F[i] to state the number of different paths starting from node i to node T.

    Initially F[T] = 1, F[others] = 0.

The transmission can be described as following:

    For i = T - 1 downto 1
        F[i] = \sum_{v = i + 1} ^ {i + N[i]}

To speed up this transmission procedure, we can use a Fenwick Tree to get the sum. But we can achieve it in a simpler way as following, using suffix sum.

    suffixSum[] = 0;
    suffixSum[T] = 1;
    For i = T - 1 downto 1
        F[i] = G[i + N[i]];
        G[i] = G[i + 1] + F[i]

To answer each query, just directly output the F[S[i]]. Therefore, the time complexity is O(N + Q) in total.

-------------------------------------------CODE------------------------------------------------------------------------

#include<bits/stdc++.h>

using namespace std;

typedef long long int lli;

int arr[1000000];

lli dp[1000000];

#define mod 1000000007

lli sum[10000000];

int main()

{

int n; cin>>n;

int t;

cin>>t;

for(int i=1;i<=n;i++)

 {

  scanf("%d",&arr[i]);

 }

 

  dp[t]=1;

  sum[t]=1;

  for(int i=t-1;i>=0;i--)

   {

      int op=arr[i];

      int  maxi=min(i+op,t);

      dp[i]=(sum[i+1]-sum[maxi+1]+mod)%mod;

      sum[i]=(sum[i+1]+dp[i])%mod;

   }

    int q;

  cin>>q;

  while(q--)

  {

     int idx;

       scanf("%d",&idx);

     cout<<dp[idx]<<endl;

  }

}