You are given an array of distinct positive integers locations where locations[i] represents the coordinate of city i. You are also given integers start, finish, and fuel, representing the starting city, the destination city, and the initial amount of fuel you have available.

At each step, if you are currently at city i, you may choose any city j such that j \neq i and move to it. Moving from city i to city j consumes $|$locations[i] $-$ locations[j]$|$ units of fuel. You cannot make a move if the required fuel exceeds your current remaining fuel.

You are permitted to visit any city multiple times, including start and finish.

Return the total number of possible routes from start to finish. Since the answer may be very large, return it modulo $10^9 + 7$.

Constraints:

• $2 \leq$ locations.length $\leq 100$

• $1 \leq$ locations[i] $\leq 10^9$

• All integers in locations are distinct.

• $0 \leq$ start, finish $<$ locations.length

• $1 \leq$ fuel $\leq 200$

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.