Pattern : 8 question Platform : Codechef u can say div-2 contest

At Motorq, real-time vehicle telemetry is forwarded through a multi-tier mesh of N gateway nodes, numbered from 1 to N.

Due to hardware topology rules, data can only flow forward: gateway i can transmit data packets directly to the next n_i consecutive gateways (i.e., gateways i + 1, i + 2, ..., i + n_i).

A valid routing path from a source gateway A to a destination hub B (A < B) is a sequence of gateways g_1, g_2, ..., g_k such that:

1. g_1 = A and g_k = B
2. Gateway g_m can directly transmit to gateway g_{m+1} for all 1 <= m < k.

Two routing paths are considered distinct if they differ in at least one intermediate gateway node.

Given a primary destination hub B and Q query source gateways, determine the total number of distinct routing paths from each source gateway A to destination hub B.

Since the number of paths can be very large, compute the result modulo 10^9 + 7.

---

Input Format

• The first line contains two space-separated integers N and B — the total number of gateways and the target destination hub ID, respectively.
• The next N lines each contain a single integer n_i — the number of forward consecutive gateways that gateway i can transmit to.
• The next line contains an integer Q — the number of query source gateways.
• The next Q lines each contain a single integer A (1 <= A < B), representing a source gateway query.

Output Format

• For each query, print a single line containing the total number of distinct routing paths from source gateway A to destination hub B modulo 10^9 + 7.

---

Constraints

• 1 <= N <= 200,000
• 1 <= B <= N
• 1 <= Q <= 100,000
• 1 <= A < B for each query A
• 1 <= i + n_i <= N for all 1 <= i <= N
• 0 <= n_i <= N - 1 for all 1 <= i <= N

---

Sample Example

Input

5 5
3
2
2
1
0
3
1
2
3

Output

6
3
2

Explanation

• Gateway Transmission Connections:

• Gateway 1 (n_1 = 3): connects to {2, 3, 4}

• Gateway 2 (n_2 = 2): connects to {3, 4}

• Gateway 3 (n_3 = 2): connects to {4, 5}

• Gateway 4 (n_4 = 1): connects to {5}

• Gateway 5 (n_5 = 0): terminal node

• Query 1 (A = 1 -> B = 5): The 6 distinct routing paths are:

1. 1 -> 2 -> 3 -> 4 -> 5
2. 1 -> 2 -> 3 -> 5
3. 1 -> 2 -> 4 -> 5
4. 1 -> 3 -> 4 -> 5
5. 1 -> 3 -> 5
6. 1 -> 4 -> 5