Imagine a city divided into zones, labeled from 0 to n.

An Uber driver follows a planned sequence of navigation instructions, where:

'l' = move one zone left (toward a lower-numbered zone).

'r' = move one zone right (toward a higher-numbered zone).

You are asked to determine: How many distinct subsequences of the driver's navigation plan allow the driver to start at zone startZone and successfully reach zone endZone? Since the number of subsequences can be large, return the result modulo (10⁹ + 7).

Notes

A subsequence is formed by deleting zero or more navigation steps without changing the order of the remaining steps.

Two subsequences are considered the same if they consist of the same navigation instructions, even if chosen from different indices.

For example, in 'rrl', the subsequence 'r' formed by deleting the first r is the same as 'r' formed by deleting the second r. Both count only once.

Starting at position j, an instruction 'l' moves to position j - 1, and an instruction 'r' moves to position j + 1.

Example

Number line positions n = 6; 0 to 6 Move sequence s: "rrlrlr" Start position (x): 1 End position (y): 4

The number of distinct subsequences of "rrlrlr" that lead from position 1 to position 4 is 3.

Function Description

Complete the function countDistinctRoutes in the editor with the following parameter(s):

string plan: the navigation sequence

int n: the upper bound of the number line

int start_zone: the starting point

int end_zone: the ending point

Returns int: the number of distinct subsequences modulo (10⁹ + 7)

Explanation Example 1:

The seven possible distinct subsequences of plan = "rrlrlr" are:

s₁ = "r", the move sequence is 1 → 2

s₂ = "rrl", the move sequence is 1 → 2 → 3 → 2

s₃ = "rlr", the move sequence is 1 → 2 → 1 → 2

s₄ = "lrr", the move sequence is 1 → 0 → 1 → 2

s₅ = "rrlrl", the move sequence is 1 → 2 → 3 → 2 → 3 → 2

s₆ = "rlrlr", the move sequence is 1 → 2 → 1 → 2 → 1 → 2

s₇ = "rrllr", the move sequence is 1 → 2 → 3 → 2 → 1 → 2