Path Counting - MotorQ Online Assessment

Problem Preview

"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** ```text 5 5 3 2 2 1 0 3 1 2 3 ``` **Output** ```text 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"