You are given an array of distinct positive integers locations where locations[i] represents the position of city i. You are also given integers start, finish and fuel representing the starting city, ending city, and the initial amount of fuel you have, respectively.
At each step, if you are at city i, you can pick any city j such that j != i and 0 <= j < locations.length and move to city j. Moving from city i to city j reduces the amount of fuel you have by |locations[i] - locations[j]|. Please notice that |x| denotes the absolute value of x.
Notice that fuel cannot become negative at any point in time, and that you are allowed to visit any city more than once (including start and finish).
Return the count of all possible routes from start to finish.
Since the answer may be too large, return it modulo 10^9 + 7.
 
Example 1:
Input: locations = [2,3,6,8,4], start = 1, finish = 3, fuel = 5
Output: 4
Explanation: The following are all possible routes, each uses 5 units of fuel:
1 -> 3
1 -> 2 -> 3
1 -> 4 -> 3
1 -> 4 -> 2 -> 3

Example 2:
Input: locations = [4,3,1], start = 1, finish = 0, fuel = 6
Output: 5
Explanation: The following are all possible routes:
1 -> 0, used fuel = 1
1 -> 2 -> 0, used fuel = 5
1 -> 2 -> 1 -> 0, used fuel = 5
1 -> 0 -> 1 -> 0, used fuel = 3
1 -> 0 -> 1 -> 0 -> 1 -> 0, used fuel = 5

Example 3:
Input: locations = [5,2,1], start = 0, finish = 2, fuel = 3
Output: 0
Explanation: It's impossible to get from 0 to 2 using only 3 units of fuel since the shortest route needs 4 units of fuel.
Example 4:
Input: locations = [2,1,5], start = 0, finish = 0, fuel = 3
Output: 2
Explanation: There are two possible routes, 0 and 0 -> 1 -> 0.
Example 5:
Input: locations = [1,2,3], start = 0, finish = 2, fuel = 40
Output: 615088286
Explanation: The total number of possible routes is 2615088300. Taking this number modulo 10^9 + 7 gives us 615088286.

 
Constraints:

2 <= locations.length <= 100
1 <= locations[i] <= 10^9
All integers in locations are distinct.
0 <= start, finish < locations.length
1 <= fuel <= 200

Source: leetcode | Difficulty: MEDIUM
Tags: Dynamic programming

Data structures

Starter code: class Solution:
    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
        

Solutions:
class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		n = len(locations)
		sloc = sorted([(x, i) for (i, x) in enumerate(locations)])
		froutes = [[0] * n for _ in range(fuel + 1)]
		(st, fn) = (-1, -1)
		for i in range(n):
			if sloc[i][1] == start:
				st = i
			if sloc[i][1] == finish:
				fn = i
		froutes[fuel][st] = 1
		f0 = fuel
		while fuel > 0:
			for (i, cnt) in enumerate(froutes[fuel]):
				if cnt > 0:
					for j in range(i - 1, -1, -1):
						dist = sloc[i][0] - sloc[j][0]
						if dist <= fuel:
							froutes[fuel - dist][j] += cnt
						else:
							break
					for j in range(i + 1, n):
						dist = sloc[j][0] - sloc[i][0]
						if dist <= fuel:
							froutes[fuel - dist][j] += cnt
						else:
							break
			fuel -= 1
		res = 0
		for i in range(f0 + 1):
			res += froutes[i][fn]
		return res % (10 ** 9 + 7)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		count = 0
		mod = 10 ** 9 + 7
		n = len(locations)
		s_l = locations[start]
		f_l = locations[finish]
		locations.sort()
		start = locations.index(s_l)
		finish = locations.index(f_l)
		import functools

		@functools.lru_cache(None)
		def DFS(cur_city, cur_fuel):
			if cur_fuel < abs(locations[cur_city] - locations[finish]):
				return 0
			if cur_city == finish:
				c = 1
			else:
				c = 0
			i = bisect.bisect_left(locations, locations[cur_city] - cur_fuel)
			j = min(n - 1, bisect.bisect_left(locations, locations[cur_city] + cur_fuel))
			for nxt in range(i, cur_city):
				c += DFS(nxt, cur_fuel - abs(locations[cur_city] - locations[nxt]))
			for nxt in range(cur_city + 1, j + 1):
				c += DFS(nxt, cur_fuel - abs(locations[cur_city] - locations[nxt]))
			return c % mod
		return DFS(start, fuel)


class Solution:

	def countRoutes(self, a: List[int], s: int, e: int, f: int) -> int:

		@lru_cache(None)
		def dfs(i, f):
			if f < 0:
				return 0
			ans = int(i == e)
			for j in range(len(a)):
				if j != i:
					ans += dfs(j, f - abs(a[i] - a[j]))
			return ans
		return dfs(s, f) % (10 ** 9 + 7)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		if not locations or fuel <= 0:
			return 0
		route_dict = {f: {} for f in range(fuel, -1, -1)}
		route_dict[fuel][start] = 1
		total_route = 0
		for f in range(fuel, 0, -1):
			for (i, num_route) in list(route_dict[f].items()):
				for j in range(len(locations)):
					if j != i:
						d = abs(locations[i] - locations[j])
						if f >= d:
							if not j in route_dict[f - d]:
								route_dict[f - d][j] = num_route
							else:
								route_dict[f - d][j] += num_route
		for f in route_dict:
			if finish in route_dict[f]:
				total_route += route_dict[f][finish]
		return total_route % (10 ** 9 + 7)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:

		@functools.lru_cache(None)
		def dp(start, fuel):
			if fuel < 0:
				return 0
			res = 0
			if start == finish:
				res += 1
			for i in range(len(locations)):
				if i != start:
					res += dp(i, fuel - abs(locations[i] - locations[start]))
			return res % (10 ** 9 + 7)
		return dp(start, fuel)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		MOD = 10 ** 9 + 7

		@lru_cache(None)
		def dp(city, fuel):
			ans = 0
			if city == finish:
				ans += 1
			for (i, c) in enumerate(locations):
				if i == city:
					continue
				cost = abs(c - locations[city])
				if cost <= fuel:
					ans += dp(i, fuel - cost)
					ans %= MOD
			return ans % MOD
		return dp(start, fuel)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		MOD = 10 ** 9 + 7

		@functools.lru_cache(None)
		def solve(i, f):
			ans = 1 if i == finish else 0
			for (j, npos) in enumerate(locations):
				cost = abs(npos - locations[i])
				if i != j and cost <= f:
					ans = (ans + solve(j, f - cost)) % MOD
			return ans
		return solve(start, fuel)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:

		@lru_cache(None)
		def step(loc, fuel_left):
			if fuel_left < 0:
				return 0
			ans = int(loc == locations[finish])
			for dest in locations:
				if dest != loc:
					ans = (ans + step(dest, fuel_left - abs(dest - loc))) % (10 ** 9 + 7)
			return ans
		return step(locations[start], fuel)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		n = len(locations)
		MOD = 1000000007

		@lru_cache(None)
		def go(pos, fuel):
			temp = 0
			if fuel < 0:
				return 0
			ans = 0
			if pos == finish:
				ans += 1
			for i in range(n):
				if i == pos:
					continue
				ans += go(i, fuel - abs(locations[pos] - locations[i]))
			return ans % MOD
		return go(start, fuel)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		dic = {}
		for (i, l) in enumerate(locations):
			dic[l] = i
		idxes = sorted(dic.keys())
		MOD = 10 ** 9 + 7
		from functools import lru_cache

		@lru_cache(None)
		def dp(i, k):
			if i == finish:
				res = 1
			else:
				res = 0
			L = bisect.bisect_left(idxes, locations[i] - k)
			R = bisect.bisect_right(idxes, locations[i] + k)
			if L == R == i:
				return res
			for j in range(L, R):
				if dic[idxes[j]] != i:
					res += dp(dic[idxes[j]], k - abs(locations[i] - idxes[j])) % MOD
			return res
		return dp(start, fuel) % MOD


from functools import lru_cache

class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:

		@lru_cache(None)
		def dp(j, f):
			summ = 0
			for (idx, loc) in enumerate(locations):
				if idx == j:
					continue
				step = abs(loc - locations[j])
				if step < f:
					if idx == start:
						summ += 1
					summ += dp(idx, f - step)
				elif step == f and idx == start:
					summ += 1
			return summ
		return dp(finish, fuel) % (10 ** 9 + 7) + (1 if start == finish else 0)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		MOD = 10 ** 9 + 7
		N = len(locations)

		@functools.lru_cache(None)
		def dfs(u, f):
			ans = 0
			if u == finish:
				ans += 1
			if f <= 0:
				return ans
			for v in range(N):
				if u == v:
					continue
				cost = abs(locations[v] - locations[u])
				if cost <= f:
					ans += dfs(v, f - cost) % MOD
			return ans
		return dfs(start, fuel) % MOD


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:

		@lru_cache(None)
		def dfs(i, f):
			res = 1 if i == e_idx else 0
			for j in range(i - 1, -1, -1):
				df = locations[i] - locations[j]
				if df > f:
					break
				res += dfs(j, f - df)
			for j in range(i + 1, len(locations)):
				df = locations[j] - locations[i]
				if df > f:
					break
				res += dfs(j, f - df)
			return res
		(s_loc, e_loc) = (locations[start], locations[finish])
		locations.sort()
		(s_idx, e_idx) = (locations.index(s_loc), locations.index(e_loc))
		return dfs(s_idx, fuel) % (10 ** 9 + 7)


MODNUM = 1000000007

class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:

		@lru_cache(None)
		def dp(i, j, f):
			if f <= 0:
				return 0
			res = 1 if i != j and abs(locations[i] - locations[j]) <= f else 0
			N = len(locations)
			for k in range(N):
				if k == j:
					continue
				dkj = abs(locations[k] - locations[j])
				if dkj < f:
					res = (res + dp(i, k, f - dkj)) % MODNUM
			return res
		return dp(start, finish, fuel) + (1 if start == finish else 0)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:

		@functools.lru_cache(None)
		def solve(s, e, f):
			res = 0 if s != e else 1
			for (i, v) in enumerate(locations):
				if i == s:
					continue
				cost = abs(locations[s] - locations[i])
				if cost > f:
					continue
				res += solve(i, e, f - cost)
			return res
		return solve(start, finish, fuel) % int(1000000000.0 + 7)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		from functools import lru_cache

		@lru_cache(None)
		def recurse(fuel, curr_city):
			if fuel == 0 and curr_city == finish:
				return 1
			if fuel == 0:
				return 0
			array = []
			for (index, city_val) in enumerate(locations):
				if curr_city != index:
					fuel_left = fuel - abs(locations[curr_city] - city_val)
					if fuel_left >= 0:
						array.append(recurse(fuel_left, index))
			if curr_city != finish:
				return sum(array)
			else:
				return sum(array) + 1
		return recurse(fuel, start) % (10 ** 9 + 7)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		mod = 10 ** 9 + 7

		@lru_cache(None)
		def dp(u, fuel):
			ans = +(u == finish)
			du = locations[u]
			for (v, dv) in enumerate(locations):
				if v != u:
					delta = abs(du - dv)
					if fuel - delta >= 0:
						ans += dp(v, fuel - delta)
						ans %= mod
			return ans
		return dp(start, fuel)


from functools import lru_cache

class Solution:

	def countRoutes(self, loc: List[int], start: int, finish: int, fuel: int) -> int:
		l = len(loc)
		MAX = 10 ** 9 + 7

		@lru_cache(None)
		def inner(curr, lf):
			if curr == finish and lf == 0:
				return 1
			if lf <= 0:
				return 0
			ans = int(curr == finish)
			for i in range(l):
				if i == curr:
					continue
				ans += inner(i, lf - abs(loc[i] - loc[curr]))
			return ans % MAX
		return inner(start, fuel)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		n = len(locations)
		f = [[0 for j in range(n)] for i in range(fuel + 1)]
		LARGE = int(1000000000.0 + 7)
		f[fuel][start] = 1
		for v in range(fuel, -1, -1):
			for (i, loc1) in enumerate(locations):
				if f[v][i] > 0:
					for (j, loc2) in enumerate(locations):
						if j != i:
							update_fuel = v - abs(loc1 - loc2)
							if update_fuel >= 0:
								f[update_fuel][j] += f[v][i] % LARGE
		result = sum([f[i][finish] for i in range(fuel)])
		if start == finish:
			result += 1
		return result % LARGE


class Solution:

	@functools.lru_cache(None)
	def core(self, start, finish, fuel):
		if fuel < 0:
			return 0
		elif abs(self.locs[start] - self.locs[finish]) > fuel:
			return 0
		elif fuel == 0:
			return 1 if start == finish else 0
		else:
			i = start - 1
			cntr = 1 if start == finish else 0
			while i >= 0:
				cost = self.locs[start] - self.locs[i]
				if 2 * cost > fuel and finish >= start or cost > fuel:
					break
				cntr += self.core(i, finish, fuel - cost)
				cntr %= self.mod
				i -= 1
				pass
			i = start + 1
			while i < len(self.locs):
				cost = self.locs[i] - self.locs[start]
				if 2 * cost > fuel and finish <= start or cost > fuel:
					break
				cntr += self.core(i, finish, fuel - cost)
				cntr %= self.mod
				i += 1
				pass
			return cntr
		pass

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		self.mod = 1000000007
		self.locs = locations
		s = locations[start]
		d = locations[finish]
		self.locs.sort()
		start = self.locs.index(s)
		finish = self.locs.index(d)
		return self.core(start, finish, fuel)


from functools import lru_cache

class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:

		@lru_cache(maxsize=None)
		def dfs(idx, f):
			cur = 0
			if f < 0:
				return cur
			if idx == finish:
				cur += 1
			for i in range(len(locations)):
				if i != idx:
					cur += dfs(i, f - abs(locations[i] - locations[idx]))
			return cur
		return dfs(start, fuel) % (10 ** 9 + 7)


from functools import lru_cache

class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		start_pos = locations[start]
		end_pos = locations[finish]
		N = len(locations)

		@lru_cache(None)
		def route(x, f):
			if abs(end_pos - x) > f:
				return 0
			if end_pos == x:
				ans = 1
			else:
				ans = 0
			for y in locations:
				if x != y:
					ans += route(y, f - abs(x - y))
			return ans
		return route(start_pos, fuel) % (10 ** 9 + 7)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		n = len(locations)
		mod = 10 ** 9 + 7

		@lru_cache(None)
		def dfs(i, f):
			if f < 0:
				return 0
			ans = i == finish
			for j in range(n):
				if i != j:
					ans += dfs(j, f - abs(locations[i] - locations[j]))
			return ans % mod
		return dfs(start, fuel)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		N = len(locations)
		mod = 10 ** 9 + 7

		@lru_cache(None)
		def rec(cur, rem):
			if rem <= 0:
				return cur == finish and rem == 0
			ans = cur == finish
			for i in range(N):
				if i == cur:
					continue
				ans += rec(i, rem - abs(locations[cur] - locations[i]))
			return ans % mod
		return rec(start, fuel)


from functools import lru_cache as l

class Solution:

	def countRoutes(self, a: List[int], s: int, t: int, fuel: int) -> int:
		n = len(a)

		@l(None)
		def dp(i, f):
			if f < 0:
				return 0
			ans = 0
			if i == t:
				ans += 1
			for j in range(n):
				if j != i:
					ans += dp(j, f - abs(a[i] - a[j]))
			return ans
		return dp(s, fuel) % (10 ** 9 + 7)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		MOD = 10 ** 9 + 7

		@lru_cache(None)
		def fn(n, x):
			if x < 0:
				return 0
			ans = 0
			if n == finish:
				ans += 1
			for nn in range(len(locations)):
				if nn != n:
					ans += fn(nn, x - abs(locations[n] - locations[nn]))
			return ans
		return fn(start, fuel) % MOD


from collections import defaultdict

class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:

		@lru_cache(None)
		def f(start, end):
			return abs(locations[start] - locations[end])

		@lru_cache(None)
		def dfs(start, finish, fuel):
			ret = 0
			for i in range(len(locations)):
				if i == start:
					continue
				f1 = fuel - f(start, i)
				if f1 >= 0:
					if i == finish:
						ret += 1
					if f(i, finish) <= f1:
						ret += dfs(i, finish, f1)
			return ret
		ret = 0
		if start == finish:
			ret = 1
		ret += dfs(start, finish, fuel)
		return ret % (10 ** 9 + 7)


import functools

class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:

		@lru_cache(maxsize=None)
		def s(city, left):
			if left < 0:
				return 0
			l = locations[city]
			(p, q) = (bisect_left(locations, l - left), bisect_right(locations, l + left))
			return (sum((s(i, left - abs(l - locations[i])) for i in range(p, q) if i != city)) + (1 if city == finish else 0)) % MOD
		(sp, fp) = (locations[start], locations[finish])
		locations.sort()
		(start, finish) = (bisect_left(locations, sp), bisect_left(locations, fp))
		MOD = 10 ** 9 + 7
		return s(start, fuel)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:

		@lru_cache(None)
		def dp(cur, fuel):
			if fuel == 0 and cur == start:
				return 1
			if fuel <= 0:
				return 0
			ways = cur == start
			for i in range(len(locations)):
				if i != cur:
					ways += dp(i, fuel - abs(locations[i] - locations[cur]))
			return ways % (10 ** 9 + 7)
		return dp(finish, fuel)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		L = len(locations)

		@lru_cache(None)
		def move(loc, remaining):
			if remaining < 0:
				return 0
			ans = 0
			if loc == finish:
				ans += 1
			for i in range(L):
				if i == loc:
					continue
				ans += move(i, remaining - abs(locations[i] - locations[loc]))
			return ans
		return move(start, fuel) % 1000000007

	def countRoutes2(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		dp = defaultdict(dict)
		for j in range(0, fuel + 1):
			for i in range(len(locations)):
				if i == finish:
					ans = 1
				else:
					ans = 0
				for k in range(len(locations)):
					if k != i:
						f = j - abs(locations[i] - locations[k])
						if f >= 0:
							ans += dp[k][f]
				dp[i][j] = ans % 1000000007
		return dp[start][fuel]


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		L = len(locations)

		@lru_cache(None)
		def move(loc, remaining):
			ans = 0
			if loc == finish:
				ans += 1
			for i in range(L):
				f = remaining
				if i == loc:
					continue
				cost = locations[i] - locations[loc]
				if cost < 0:
					cost = -cost
				f -= cost
				if f < 0:
					continue
				ans += move(i, f)
			return ans
		return move(start, fuel) % 1000000007

	def countRoutes2(self, l: List[int], start: int, fin: int, fuel: int) -> int:

		@lru_cache(None)
		def dfs(i: int, f: int) -> int:
			if f < 0:
				return 0
			ans = 0
			if i == fin:
				ans = 1
			ans += sum((0 if i == j else dfs(j, f - abs(l[j] - l[i])) for j in range(len(l))))
		return dfs(start, fuel) % 1000000007


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		dp = [[0 for j in range(len(locations))] for i in range(fuel + 1)]
		dp[fuel][start] = 1
		for i in range(fuel, -1, -1):
			for j in range(len(locations) - 1, -1, -1):
				if dp[i][j] == 0:
					continue
				for st in range(len(locations)):
					if st != j:
						if i >= abs(locations[st] - locations[j]):
							dp[i - abs(locations[st] - locations[j])][st] += dp[i][j]
		total = 0
		for i in range(fuel + 1):
			total += dp[i][finish]
		return total % (10 ** 9 + 7)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:

		@lru_cache(None)
		def dp(i, f):
			if f < 0:
				return 0
			return (sum((dp(j, f - abs(locations[i] - locations[j])) for j in range(len(locations)) if i != j)) + (i == finish)) % (10 ** 9 + 7)
		return dp(start, fuel)


class Solution:

	def countRoutes(self, A: List[int], start: int, finish: int, fuel: int) -> int:
		(n, mod) = (len(A), 10 ** 9 + 7)

		@functools.lru_cache(None)
		def dfs(i, f):
			ret = 1 if i == finish else 0
			for j in range(n):
				if i != j and abs(A[i] - A[j]) <= f:
					ret += dfs(j, f - abs(A[i] - A[j]))
			return ret
		return dfs(start, fuel) % mod


class Solution:

	def countRoutes(self, locs: List[int], start: int, finish: int, fuel: int) -> int:

		@lru_cache(None)
		def dfs(i: int, f: int) -> int:
			res = 1 if i == finish else 0
			for j in range(len(locs)):
				if i != j and f >= abs(locs[j] - locs[i]):
					res += dfs(j, f - abs(locs[j] - locs[i]))
			return res % 1000000007
		return dfs(start, fuel)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		start_pos = locations[start]
		finish_pos = locations[finish]
		locations.sort()
		for (i, location) in enumerate(locations):
			if location == start_pos:
				start = i
			if location == finish_pos:
				finish = i
		print(locations)
		print((start, finish, fuel))

		@lru_cache(None)
		def dfs(i, j, f):
			if f < 0:
				return 0
			if abs(locations[i] - locations[j]) > f:
				return 0
			l = locations[i] - f
			r = locations[i] + f
			li = bisect.bisect_left(locations, l)
			ri = bisect.bisect_right(locations, r)
			ans = 1 if i == j else 0
			for k in range(li, ri):
				if k != i:
					ans += dfs(k, j, f - abs(locations[i] - locations[k]))
			return ans
		return dfs(start, finish, fuel) % (10 ** 9 + 7)


class Solution:

	def countRoutes(self, loc: List[int], s: int, f: int, fuel: int) -> int:
		n = len(loc)

		@lru_cache(None)
		def t(s, f, fuel):
			if fuel < 0:
				return 0
			ct = s == f
			for i in range(n):
				if i != s:
					ct += t(i, f, fuel - abs(loc[s] - loc[i]))
			return ct
		return t(s, f, fuel) % (10 ** 9 + 7)


class Solution:

	def countRoutes(self, A: List[int], start: int, finish: int, fuel: int) -> int:
		N = len(A)
		MOD = 10 ** 9 + 7

		@functools.lru_cache(None)
		def dp(i, rem):
			if rem == 0:
				return 0
			ways = 0
			for j in range(N):
				deltaF = rem - abs(A[i] - A[j])
				if i != j and deltaF >= 0:
					ways = (ways + dp(j, deltaF)) % MOD
					if j == finish:
						ways = (ways + 1) % MOD
			return ways
		return dp(start, fuel) + (1 if start == finish else 0)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		mod = 10 ** 9 + 7

		@lru_cache(None)
		def dp(curr, fuel):
			nonlocal mod
			if fuel < 0:
				return 0
			ans = 0
			if curr == finish:
				ans += 1
			if fuel < 0:
				return 0
			for i in range(len(locations)):
				if i == curr or fuel < abs(locations[i] - locations[curr]):
					continue
				ans += dp(i, fuel - abs(locations[i] - locations[curr]))
			return ans
		return dp(start, fuel) % mod


class Solution:

	def countRoutes(self, loc: List[int], start: int, finish: int, fuel: int) -> int:

		@lru_cache(None)
		def get(cur, left):
			if left < 0:
				return 0
			return (sum([get(i, left - abs(loc[i] - loc[cur])) for i in range(len(loc)) if i != cur]) + (cur == finish)) % 1000000007
		return get(start, fuel)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		n = len(locations)

		@lru_cache(None)
		def helper(ind, f):
			ret = 0
			if ind == finish:
				ret += 1
			for i in range(n):
				if i != ind and abs(locations[i] - locations[ind]) <= f:
					ret += helper(i, f - abs(locations[i] - locations[ind]))
			return ret
		return helper(start, fuel) % (10 ** 9 + 7)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		n = len(locations)
		kMod = 1000000000.0 + 7

		@lru_cache(None)
		def dp(i, f):
			if f < 0:
				return 0
			return (sum([dp(j, f - abs(locations[j] - locations[i])) for j in range(n) if j != i]) + (i == finish)) % kMod
		return int(dp(start, fuel))


import functools

class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:

		@functools.lru_cache(None)
		def doit(start, fuel):
			if fuel < 0:
				return 0
			ans = 0
			if start == finish and fuel >= 0:
				ans += 1
			for i in range(len(locations)):
				if i != start and fuel >= abs(locations[i] - locations[start]):
					ans += doit(i, fuel - abs(locations[i] - locations[start]))
			return ans % 1000000007
		return doit(start, fuel)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:

		@lru_cache(None)
		def dfs(i: int, f: int) -> int:
			if f < 0:
				return 0
			return (1 if i == finish else 0) + sum((0 if i == j else dfs(j, f - abs(locations[j] - locations[i])) for j in range(len(locations))))
		return dfs(start, fuel) % 1000000007


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		n = len(locations)
		dp = [[0] * (fuel + 1) for _ in range(n)]
		dp[start][fuel] = 1
		for f in range(fuel, 0, -1):
			for i in range(0, n):
				if dp[i][f] == 0 or abs(locations[i] - locations[finish]) > f:
					continue
				for j in range(0, n):
					d = abs(locations[i] - locations[j])
					if i == j or d == 0 or d > f:
						continue
					dp[j][f - d] = (dp[j][f - d] + dp[i][f]) % 1000000007
		return sum(dp[finish]) % 1000000007


from functools import lru_cache

class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		MOD = 10 ** 9 + 7

		@lru_cache(None)
		def DP(cur, fuel):
			if fuel < 0:
				return 0
			return (int(cur == finish) + sum((DP(nxt, fuel - abs(locations[cur] - locations[nxt])) for nxt in range(len(locations)) if nxt != cur))) % MOD
		return DP(start, fuel)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		n = len(locations)
		m = [[0 for i in range(n)] for j in range(n)]
		for i in range(n):
			for j in range(i + 1, n):
				cost = abs(locations[i] - locations[j])
				m[i][j] = cost
				m[j][i] = cost
		mod = int(1000000000.0 + 7)
		memo = [[-1 for i in range(n)] for j in range(fuel + 1)]

		def DFS(start, finish, f):
			if memo[f][start] != -1:
				return memo[f][start]
			if f < 0:
				return 0
			res = 0
			if start == finish:
				res += 1
			for i in range(n):
				if i != start and m[start][i] <= f:
					res = (res + DFS(i, finish, f - m[start][i])) % mod
			memo[f][start] = res
			return res
		return DFS(start, finish, fuel)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		n = len(locations)

		@lru_cache(maxsize=None)
		def dp(cur, finish, fuel):
			if fuel < 0:
				return 0
			ans = 1 if cur == finish else 0
			for (nextCity, val) in enumerate(locations):
				if nextCity != cur:
					ans += dp(nextCity, finish, fuel - abs(val - locations[cur]))
			return ans % (10 ** 9 + 7)
		return dp(start, finish, fuel)


from functools import lru_cache

class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		MOD = 10 ** 9 + 7

		@lru_cache(None)
		def dfs(curr, fuel):
			if fuel < 0:
				return 0
			res = 1 if curr == finish else 0
			for (i, loc) in enumerate(locations):
				if i == curr:
					continue
				fuel_used = abs(loc - locations[curr])
				res += dfs(i, fuel - fuel_used)
			return res % MOD
		res = dfs(start, fuel)
		return res % MOD


class Solution:

	def countRoutes(self, locations, start: int, finish: int, fuel: int) -> int:

		def dfs(index, current_fuel):
			if not current_fuel and index == finish:
				return 1
			paths = index == finish
			for (i, n) in enumerate(locations):
				if i != index:
					tmp_fuel = current_fuel - abs(locations[index] - n)
					if (i, tmp_fuel) in memo:
						paths += memo[i, tmp_fuel]
					elif tmp_fuel >= 0:
						paths += dfs(i, tmp_fuel)
			memo[index, current_fuel] = paths
			return paths
		memo = {}
		return dfs(start, fuel) % (10 ** 9 + 7)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		M = 1000000007

		@lru_cache(None)
		def f(idx, fuel):
			if fuel < 0:
				return 0
			cnt = 1 if idx == start else 0
			for (i, val) in enumerate(locations):
				if i == idx:
					continue
				if abs(val - locations[idx]) <= fuel:
					cnt = (cnt + f(i, fuel - abs(val - locations[idx]))) % M
			return cnt % M
		return f(finish, fuel)


sys.setrecursionlimit(1000000)

class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		MOD = 10 ** 9 + 7
		(start, finish) = (locations[start], locations[finish])
		if abs(finish - start) > fuel:
			return 0
		locations = [x for x in locations if abs(x - start) <= fuel]

		@lru_cache(None)
		def dfs(u, fuel):
			res = 0
			if u == finish:
				res += 1
			for v in locations:
				if v != u:
					cost = abs(v - u)
					if cost <= fuel:
						res += dfs(v, fuel - cost)
			return res % MOD
		return dfs(start, fuel)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		return foo(locations, start, finish, fuel)
from functools import lru_cache

def foo(cities, start, end, f):
	n = len(cities)

	@lru_cache(maxsize=None)
	def bar(i, f):
		rv = 0
		if f < 0:
			return 0
		if i == end:
			rv += 1
		return rv + sum((bar(j, f - abs(cities[j] - cities[i])) for j in range(n) if i != j))
	return bar(start, f) % (10 ** 9 + 7)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		mod = 10 ** 9 + 7

		@lru_cache(None)
		def dfs(i, j, f):
			res = 0
			if i == j:
				res += 1
			if f < 0:
				return 0
			for k in range(len(locations)):
				if i == k:
					continue
				res += dfs(k, j, f - abs(locations[k] - locations[i]))
			return res
		return dfs(start, finish, fuel) % mod


class Solution:

	def countRoutes(self, loc: List[int], start: int, finish: int, fuel: int) -> int:

		@functools.lru_cache(None)
		def helper(i, f):
			if i == finish:
				return 1 + sum((helper(j, f - abs(loc[i] - loc[j])) for j in range(len(loc)) if j != i and f >= abs(loc[i] - loc[j])))
			return sum((helper(j, f - abs(loc[i] - loc[j])) for j in range(len(loc)) if j != i and f >= abs(loc[i] - loc[j])))
		return helper(start, fuel) % (10 ** 9 + 7)


from functools import lru_cache
import bisect

class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		mod = 10 ** 9 + 7
		start_pos = locations[start]
		finish_pos = locations[finish]
		locations.sort()
		i = bisect.bisect_left(locations, start_pos)
		j = bisect.bisect_left(locations, finish_pos)
		n = len(locations)

		@lru_cache(None)
		def ways(i, j, fuel):
			if fuel < abs(locations[i] - locations[j]):
				return 0
			res = 0
			l = r = 1
			if i == j:
				res += 1
			while i - l >= 0:
				if fuel - abs(locations[i - l] - locations[j]) < 0:
					break
				res += ways(i - l, j, fuel - abs(locations[i - l] - locations[i]))
				res %= mod
				l += 1
			while i + r < n:
				if fuel - abs(locations[i + r] - locations[j]) < 0:
					break
				res += ways(i + r, j, fuel - abs(locations[i + r] - locations[i]))
				res %= mod
				r += 1
			return res % mod
		return ways(i, j, fuel)


from functools import lru_cache

class Solution:
	M = 10 ** 9 + 7

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:

		@lru_cache(maxsize=None)
		def R(dest, f):
			if f > 0:
				return (sum((R(i, f - abs(locations[i] - locations[dest])) for i in range(len(locations)) if i != dest)) + int(dest == start)) % self.M
			return int(f == 0 and dest == start)
		return R(finish, fuel)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		m = len(locations)
		n = fuel + 1
		dp = [[0] * n for _ in range(m)]
		dp[start][fuel] = 1
		for fuel in reversed(range(1, n)):
			for end in range(m):
				if dp[end][fuel] > 0:
					for nxt in range(m):
						cost = abs(locations[end] - locations[nxt])
						if fuel >= cost and end != nxt:
							dp[nxt][fuel - cost] += dp[end][fuel]
		return sum(dp[finish]) % (int(1000000000.0) + 7)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		MOD = 10 ** 9 + 7

		@functools.lru_cache(maxsize=None)
		def dp(city: int, tank: int) -> int:
			return ((1 if city == finish else 0) + sum((dp(i, tank - abs(locations[city] - locations[i])) for i in range(len(locations)) if i != city))) % MOD if tank >= 0 else 0
		return dp(start, fuel)


class Solution:

	def countRoutes(self, A, s: int, e: int, fuel) -> int:

		@lru_cache(None)
		def dfs(i: int, f: int) -> int:
			return 0 if f < 0 else (1 if i == e else 0) + sum((0 if i == j else dfs(j, f - abs(A[j] - A[i])) for j in range(len(A))))
		return dfs(s, fuel) % 1000000007


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		dp = [[-1] * (fuel + 1) for i in range(len(locations))]

		def dfs(start, fuel):
			if fuel < 0:
				return 0
			if dp[start][fuel] > -1:
				return dp[start][fuel]
			if start == finish:
				res = 1
			else:
				res = 0
			for i in range(len(locations)):
				if i != start:
					res += dfs(i, fuel - abs(locations[i] - locations[start]))
			dp[start][fuel] = res % (10 ** 9 + 7)
			return dp[start][fuel]
		return dfs(start, fuel)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		R = 10 ** 9 + 7
		N = len(locations)

		@functools.lru_cache(maxsize=None)
		def dp(i, fuel):
			res = 1 if i == finish else 0
			for j in range(N):
				if j != i:
					cost = abs(locations[i] - locations[j])
					if fuel >= cost:
						res = (res + dp(j, fuel - cost)) % R
			return res
		return dp(start, fuel)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		from functools import lru_cache

		@lru_cache(None)
		def solve(curCity, fuel):
			if fuel < 0:
				return 0
			ans = 1 if curCity == finish else 0
			for nextCity in range(0, len(locations)):
				if nextCity != curCity:
					ans = (ans + solve(nextCity, fuel - abs(locations[curCity] - locations[nextCity]))) % 1000000007
			return ans
		return solve(start, fuel)


from functools import lru_cache

class Solution:

	def countRoutes(self, A: List[int], start: int, finish: int, fuel: int) -> int:

		@lru_cache(None)
		def helper(i, fuel):
			if fuel < 0:
				return 0
			res = 0
			if i == finish:
				res += 1
			for nxt in range(len(A)):
				if nxt != i:
					res = (res + helper(nxt, fuel - abs(A[i] - A[nxt]))) % 1000000007
			return res
		return helper(start, fuel)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		from functools import lru_cache

		@lru_cache(None)
		def helper(loc, fuel):
			if loc == finish and fuel == 0:
				return 1
			elif loc != finish and fuel == 0:
				return 0
			s = 0
			if loc == finish:
				s = 1
			for i in range(length):
				if i == loc:
					continue
				dist = abs(locations[i] - locations[loc])
				if dist <= fuel:
					s = (s + helper(i, fuel - dist)) % MOD
			return s
		MOD = 10 ** 9 + 7
		length = len(locations)
		return helper(start, fuel)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		n = len(locations)
		mod = 10 ** 9 + 7

		@lru_cache(None)
		def go(x, remain):
			if remain < 0:
				return 0
			ret = 0
			if x == finish:
				ret = 1
			for i in range(0, n):
				if i == x:
					continue
				ret += go(i, remain - abs(locations[x] - locations[i]))
				ret %= mod
			return ret % mod
		ans = go(start, fuel) % mod
		return ans


class Solution:

	def countRoutes(self, l: List[int], st: int, fin: int, fuel: int) -> int:

		@lru_cache(None)
		def dfs(i, f):
			return 0 if f < 0 else (1 if i == fin else 0) + sum((0 if i == j else dfs(j, f - abs(l[i] - l[j])) for j in range(len(l))))
		return dfs(st, fuel) % 1000000007


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		ln = len(locations)
		mod = 10 ** 9 + 7

		@functools.lru_cache(None)
		def dp(cur, fuel):
			if fuel < 0:
				return 0
			ans = 1 if cur == finish else 0
			for city in range(ln):
				if city != cur:
					ans += dp(city, fuel - abs(locations[city] - locations[cur]))
					ans %= mod
			return ans
		return dp(start, fuel)


class Solution:

	def countRoutes(self, locations: 'List[int]', start: int, finish: int, fuel: int) -> int:
		MOD = 1000000007
		(sp, ep) = (locations[start], locations[finish])
		locations.sort()
		(s, e) = (locations.index(sp), locations.index(ep))
		if s > e:
			(s, e) = (e, s)
		N = len(locations)

		@functools.lru_cache(None)
		def helper(i, f):
			if i != e and locations[e] - locations[i] <= f:
				res = 1
			else:
				res = 0
			k = i - 1
			while k >= 0 and locations[i] + locations[e] - 2 * locations[k] <= f:
				res += helper(k, f - (locations[i] - locations[k]))
				k -= 1
			k = i + 1
			while k < N and locations[k] - locations[i] + abs(locations[k] - locations[e]) <= f:
				res += helper(k, f - (locations[k] - locations[i]))
				k += 1
			return res % MOD
		return helper(s, fuel) + (s == e)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		(N, R) = (len(locations), 10 ** 9 + 7)
		dp = [[-1] * (fuel + 1) for _ in range(N)]

		def _dfs(p, f):
			if dp[p][f] < 0:
				dp[p][f] = 0
				for q in range(N):
					if q == p:
						continue
					left = f - abs(locations[p] - locations[q])
					if left < abs(locations[finish] - locations[q]):
						continue
					dp[p][f] += _dfs(q, left)
				dp[p][f] += 1 if p == finish else 0
			return dp[p][f] % R
		return _dfs(start, fuel)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		MOD = 10 ** 9 + 7
		n = len(locations)
		graph = defaultdict(list)
		for i in range(n):
			for j in range(i + 1, n):
				cost = abs(locations[i] - locations[j])
				graph[i].append((j, cost))
				graph[j].append((i, cost))

		@lru_cache(None)
		def dfs(i, budget):
			if budget < 0:
				return 0
			res = 1 if i == finish else 0
			if budget == 0:
				return res
			for (nei, cost) in graph[i]:
				res += dfs(nei, budget - cost)
				res %= MOD
			return res
		res = dfs(start, fuel)
		return res % MOD


class Solution:

	def countRoutes(self, arr: List[int], start: int, finish: int, fuel: int) -> int:
		n = len(arr)
		mod = 10 ** 9 + 7

		@lru_cache(None)
		def f(curr, fu):
			ans = int(curr == finish)
			for i in range(n):
				if i != curr:
					if abs(arr[i] - arr[curr]) <= fu:
						ans += f(i, fu - abs(arr[i] - arr[curr]))
						ans %= mod
			return ans
		return f(start, fuel)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		dp = [[-1] * (fuel + 1) for _ in range(len(locations))]

		def f(cur, cur_fuel):
			if dp[cur][cur_fuel] != -1:
				return dp[cur][cur_fuel]
			total = 1 if cur == finish else 0
			for (i, location) in enumerate(locations):
				if i == cur:
					continue
				dist = abs(locations[i] - locations[cur])
				if dist <= cur_fuel:
					total += f(i, cur_fuel - dist)
			dp[cur][cur_fuel] = total
			return total
		return f(start, fuel) % 1000000007


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		dp = [[0 for x in range(len(locations))] for _ in range(fuel + 1)]
		dp[0][start] = 1
		for i in range(1, fuel + 1):
			for j in range(len(locations)):
				for k in range(len(locations)):
					if j != k:
						need = abs(locations[j] - locations[k])
						if need <= i:
							dp[i][j] += dp[i - need][k]
		ans = 0
		for i in range(fuel + 1):
			ans += dp[i][finish]
		return ans % (10 ** 9 + 7)

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		M = 10 ** 9 + 7

		@lru_cache(None)
		def helper(curr_city, curr_fuel):
			if curr_fuel < 0:
				return 0
			ans = 0
			if curr_city == finish:
				ans += 1
			for i in range(len(locations)):
				if i != curr_city:
					ans += helper(i, curr_fuel - abs(locations[i] - locations[curr_city]))
					ans %= M
			return ans
		return helper(start, fuel)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:

		@lru_cache(maxsize=None)
		def count(start: int, fuel: int, MOD=10 ** 9 + 7) -> int:
			if fuel < 0:
				return 0
			elif fuel == 0 and start == finish:
				return 1
			else:
				ways = 1 if start == finish else 0
				for (i, loc) in enumerate(locations):
					if i != start:
						ways = (ways + count(i, fuel - abs(loc - locations[start]))) % MOD
				return ways
		return count(start, fuel)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:

		@lru_cache(None)
		def dfs(x, y, f):
			if abs(A[x] - A[y]) > f:
				return 0
			ret = 0
			if abs(A[x] - A[y]) <= f:
				ret += 1
			for mid in range(n):
				g = abs(A[mid] - A[x]) + abs(A[mid] - A[y])
				if mid == x or g > f:
					continue
				ret += dfs(mid, y, f - abs(A[mid] - A[x]))
				if mid == y:
					ret -= 1
				ret %= MOD
			return ret
		A = locations
		n = len(A)
		MOD = 10 ** 9 + 7
		return dfs(start, finish, fuel)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		n = len(locations)

		@functools.lru_cache(None)
		def dp(i, f):
			ans = 0 if i != finish else 1
			for j in range(n):
				if i == j:
					continue
				ff = abs(locations[i] - locations[j])
				if f >= ff:
					ans += dp(j, f - ff)
			return ans % (10 ** 9 + 7)
		return dp(start, fuel)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:

		def go(pos, f, dp):
			if f == 0:
				return 1 if pos == finish else 0
			if dp[pos][f] > -1:
				return dp[pos][f]
			ans = 1 if pos == finish else 0
			for (idx, loc) in enumerate(locations):
				if idx != pos:
					c = abs(locations[pos] - loc)
					ans += go(idx, f - c, dp) if f >= c else 0
			dp[pos][f] = ans
			return ans
		memo = [[-1] * (fuel + 1) for _ in locations]
		memo[finish][0] = 1
		return go(start, fuel, memo) % 1000000007


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		N = len(locations)
		mod = 1000000007

		@lru_cache(None)
		def dfs(city, fuel):
			c = int(city == finish)
			for i in range(N):
				if i != city:
					cost = abs(locations[i] - locations[city])
					if cost <= fuel:
						c = (c + dfs(i, fuel - cost)) % mod
			return c
		return dfs(start, fuel)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:

		@lru_cache(None)
		def dfs(start, finish, fuel):
			if fuel < 0:
				return 0
			routes = 1 if start == finish else 0
			for (i, location) in enumerate(locations):
				if i == start:
					continue
				routes += dfs(i, finish, fuel - abs(locations[i] - locations[start]))
			return routes
		return dfs(start, finish, fuel) % (10 ** 9 + 7)


import sys
from functools import lru_cache
sys.setrecursionlimit(10 ** 6)

class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:

		@lru_cache(None)
		def chal(st, fi, x):
			if x < 0:
				return 0
			if st == fi:
				ans = 1
			else:
				ans = 0
			for i in range(0, len(locations)):
				if i != st:
					ans += chal(i, fi, x - abs(locations[i] - locations[st])) % (10 ** 9 + 7)
			return ans % (10 ** 9 + 7)
		return chal(start, finish, fuel)


import functools

class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:

		@functools.lru_cache(10 ** 9)
		def findRoutes(start, finish, fuel, n):
			r = 0
			if fuel < 0:
				return 0
			if start == finish:
				r += 1
			for i in range(n):
				if i != start:
					r += findRoutes(i, finish, fuel - abs(locations[i] - locations[start]), n)
			return r
		return findRoutes(start, finish, fuel, len(locations)) % (10 ** 9 + 7)


class Solution:

	def countRoutes(self, loc: List[int], start: int, finish: int, fuel: int) -> int:

		@lru_cache(None)
		def dp(i, gas):
			if gas < abs(loc[i] - loc[finish]):
				return 0
			ans = 0
			if i == finish:
				ans += 1
			for nxt in range(len(loc)):
				if nxt != i:
					ans += dp(nxt, gas - abs(loc[i] - loc[nxt]))
			return ans
		res = dp(start, fuel)
		return res % (10 ** 9 + 7)


class Solution:

	def countRoutes(self, locacs: List[int], start: int, finish: int, fuel: int) -> int:
		dp = [[-1] * (fuel + 1) for _ in range(len(locacs))]

		def go(at, f):
			if f <= 0:
				return 1 if at == finish else 0
			if dp[at][f] >= 0:
				return dp[at][f]
			ans = 1 if at == finish else 0
			for (to, loc) in enumerate(locacs):
				if to == at:
					continue
				c = abs(locacs[at] - loc)
				ans += go(to, f - c) if f >= c else 0
			dp[at][f] = ans
			return ans
		return go(start, fuel) % (10 ** 9 + 7)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:

		@lru_cache(None)
		def go(i, f):
			if f < 0:
				return 0
			if f == 0:
				if i == finish:
					return 1
				return 0
			count = 0
			if i == finish:
				count += 1
			for j in range(len(locations)):
				if i != j:
					count += go(j, f - abs(locations[i] - locations[j]))
			return count
		return go(start, fuel) % (10 ** 9 + 7)


from functools import lru_cache

class Solution:

	@lru_cache(None)
	def dp(self, start, fuel):
		r = 0
		if fuel < 0:
			return 0
		if start == self.finish:
			r += 1
		for l in self.locations:
			if start == l:
				continue
			r += self.dp(l, fuel - abs(start - l))
		return r

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		self.finish = locations[finish]
		self.locations = locations
		return self.dp(locations[start], fuel) % (10 ** 9 + 7)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		n = len(locations)
		MOD = 10 ** 9 + 7

		@lru_cache(None)
		def dp(used, node):
			if used > fuel:
				return 0
			res = 1 if node == finish else 0
			for nxt in range(n):
				if node == nxt:
					continue
				nused = used + abs(locations[node] - locations[nxt])
				res += dp(nused, nxt) % MOD
			return res
		return dp(0, start) % MOD


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		dp = [[-1 for _ in range(fuel + 1)] for _ in locations]

		def search(start, fuel):
			if fuel == 0:
				if start == finish:
					return 1
				return 0
			if dp[start][fuel] != -1:
				return dp[start][fuel]
			dp[start][fuel] = 1 if start == finish else 0
			for i in range(len(locations)):
				left = fuel - abs(locations[i] - locations[start])
				if i != start and left >= 0:
					dp[start][fuel] += search(i, left)
			return dp[start][fuel] % 1000000007
		search(start, fuel)
		return dp[start][fuel] % 1000000007


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		if abs(locations[start] - locations[finish]) > fuel:
			return 0
		mod = 10 ** 9 + 7

		@lru_cache(None)
		def dfs(node, fu):
			an = 0
			if node == finish:
				an += 1
			for i in range(len(locations)):
				if i != node and abs(locations[node] - locations[i]) <= fu:
					an += dfs(i, fu - abs(locations[node] - locations[i]))
			return an
		return dfs(start, fuel) % mod


from functools import lru_cache

class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		mod = 10 ** 9 + 7

		@lru_cache(None)
		def dfs(pos, f):
			out = 0
			if pos == finish:
				out += 1
			for (i, x) in enumerate(locations):
				if i != pos and f >= abs(x - locations[pos]):
					out += dfs(i, f - abs(x - locations[pos]))
					out %= mod
			return out
		return dfs(start, fuel)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		modulo = 10 ** 9 + 7
		n = len(locations)
		(start_pos, finish_pos) = (locations[start], locations[finish])
		locations.sort()
		start = locations.index(start_pos)
		finish = locations.index(finish_pos)

		@lru_cache(None)
		def dp(cur, fuel):
			res = 0
			if cur == finish:
				res += 1
			for nxt in range(cur + 1, n):
				if nxt < 0 or nxt >= n:
					continue
				if abs(locations[nxt] - locations[cur]) > fuel:
					break
				res += dp(nxt, fuel - abs(locations[nxt] - locations[cur]))
			for nxt in range(cur - 1, -1, -1):
				if nxt < 0 or nxt >= n:
					continue
				if abs(locations[nxt] - locations[cur]) > fuel:
					break
				res += dp(nxt, fuel - abs(locations[nxt] - locations[cur]))
			return res % modulo
		return dp(start, fuel)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		memo = {}

		def dfs(x, left_fuel):
			if (x, left_fuel) in memo:
				return memo[x, left_fuel]
			s = 0
			if x == finish:
				s += 1
			for i in range(len(locations)):
				if x == i:
					continue
				needed = abs(locations[x] - locations[i])
				if left_fuel >= needed:
					s += dfs(i, left_fuel - needed)
			memo[x, left_fuel] = s
			return s
		return dfs(start, fuel) % (10 ** 9 + 7)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		ans = 0
		MOD = 10 ** 9 + 7

		def fun(ind, arr, rem, target):
			if dp[ind][rem] != None:
				return dp[ind][rem]
			cnt = 0
			if ind == target:
				cnt += 1
			for (i, val) in enumerate(arr):
				if i == ind:
					continue
				if abs(arr[ind] - val) <= rem:
					cnt += fun(i, arr, rem - abs(arr[ind] - val), target)
			dp[ind][rem] = cnt % (10 ** 9 + 7)
			return dp[ind][rem]
		dp = [[None] * (1 + fuel) for _ in range(len(locations))]
		return fun(start, locations, fuel, finish)


class Solution:

	def countRoutes(self, a: List[int], start: int, finish: int, fuel: int) -> int:
		mod = 10 ** 9 + 7
		ans = 0
		start = a[start]
		finish = a[finish]

		@lru_cache(None)
		def solve(c, f):
			if f < 0:
				return 0
			ans = 0
			if c == finish:
				ans += 1
			for x in a:
				if x == c:
					continue
				ans += solve(x, f - abs(x - c))
			return ans % mod
		return solve(start, fuel)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		dp = [[-1] * (fuel + 1) for _ in range(len(locations))]

		def route(st, ed, fuel):
			if dp[st][fuel] > -1:
				return dp[st][fuel]
			res = 0 if st != ed else 1
			for i in range(len(locations)):
				if i != st and fuel - abs(locations[st] - locations[i]) >= 0:
					res += route(i, ed, fuel - abs(locations[st] - locations[i]))
			dp[st][fuel] = res % 1000000007
			return dp[st][fuel]
		return route(start, finish, fuel)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:

		def helper(c, f):
			if (c, f) not in d:
				t = c == finish
				if f > 0:
					for i in range(len(locations)):
						u = abs(locations[i] - locations[c])
						if i != c and u <= f:
							t += helper(i, f - u)
				d[c, f] = t % 1000000007
			return d[c, f]
		d = {}
		return helper(start, fuel)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		cache = {}

		def dp(i, fuel):
			if (i, fuel) in cache:
				return cache[i, fuel]
			count = 1 if i == finish else 0
			for j in range(len(locations)):
				if i != j:
					dist = abs(locations[i] - locations[j])
					if dist <= fuel:
						count += dp(j, fuel - dist)
			cache[i, fuel] = count
			return count
		return dp(start, fuel) % (10 ** 9 + 7)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		dp = {}

		def recursive(curr, fuel):
			if (curr, fuel) in dp:
				return dp[curr, fuel]
			count = 1 if curr == finish else 0
			for c in range(len(locations)):
				fuelRequired = abs(locations[c] - locations[curr])
				if c != curr and fuel >= fuelRequired:
					count += recursive(c, fuel - fuelRequired)
			dp[curr, fuel] = count % (10 ** 9 + 7)
			return dp[curr, fuel]
		return recursive(start, fuel)


class Solution:

	@lru_cache(1024 * 1024)
	def helper(self, fuel_left, curr, target):
		su = 0
		if curr == target:
			su += 1
		for i in range(len(self.locations)):
			if i == curr:
				continue
			spent = abs(self.locations[curr] - self.locations[i])
			if fuel_left >= spent:
				su += self.helper(fuel_left - spent, i, target)
		return su

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		self.locations = locations
		return self.helper(fuel, start, finish) % 1000000007


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		mod = 10 ** 9 + 7
		n = len(locations)

		@lru_cache(None)
		def dfs(cur, remain):
			if abs(locations[finish] - locations[cur]) > remain:
				return 0
			res = 0
			if cur == finish:
				res = 1
			for i in range(n):
				if i == cur:
					continue
				temp = abs(locations[i] - locations[cur])
				if temp <= remain:
					res = (res + dfs(i, remain - temp)) % mod
			return res
		return dfs(start, fuel)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		mod = 10 ** 9 + 7

		def dfs(i, f, dp):
			key = (i, f)
			if key in dp:
				return dp[key]
			ans = 1 if i == finish else 0
			li = locations[i]
			for (j, l) in enumerate(locations):
				if j == i:
					continue
				cost = abs(l - li)
				if cost > f:
					continue
				ans = (ans + dfs(j, f - cost, dp)) % mod
			dp[key] = ans
			return ans
		return dfs(start, fuel, {})


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		memo = {}

		def dfs(u, fuel):
			if (u, fuel) in memo:
				return memo[u, fuel]
			ans = 1 if u == finish else 0
			for v in range(len(locations)):
				cost = abs(locations[u] - locations[v])
				if cost > 0 and cost <= fuel:
					ans += dfs(v, fuel - cost)
			ans %= 1000000007
			memo[u, fuel] = ans
			return ans
		return dfs(start, fuel)


class Solution:

	def helper(self, locations, index, finish, fuelLeft, cache):
		if (index, fuelLeft) in cache:
			return cache[index, fuelLeft]
		result = 0
		if index == finish and fuelLeft >= 0:
			result += 1
		for i in range(len(locations)):
			if i == index:
				continue
			fuelUsed = abs(locations[index] - locations[i])
			if fuelLeft >= fuelUsed:
				result += self.helper(locations, i, finish, fuelLeft - fuelUsed, cache)
		cache[index, fuelLeft] = result
		return result

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		result = self.helper(locations, start, finish, fuel, {})
		return result % (10 ** 9 + 7)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		dp = {}

		def recursive(curr, fuel):
			count = 0
			if (curr, fuel) in dp:
				return dp[curr, fuel]
			elif curr == finish:
				count += 1
			for c in range(len(locations)):
				fuelRequired = abs(locations[c] - locations[curr])
				if c != curr and fuel >= fuelRequired:
					count += recursive(c, fuel - fuelRequired)
			dp[curr, fuel] = count % 1000000007
			return dp[curr, fuel]
		return recursive(start, fuel)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		md = 10 ** 9 + 7
		n = len(locations)
		dp = [[0] * (fuel + 1) for _ in range(n)]
		dp[start][0] = 1
		for j in range(fuel):
			for i in range(n):
				pre = dp[i][j] % md
				if pre == 0:
					continue
				for ni in range(n):
					if i == ni:
						continue
					nj = j + abs(locations[i] - locations[ni])
					if nj > fuel:
						continue
					dp[ni][nj] += pre
		ans = sum(dp[finish]) % md
		return ans


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		if abs(locations[start] - locations[finish]) > fuel:
			return 0
		lc = len(locations)
		mod = 10 ** 9 + 7

		@lru_cache(None)
		def rec_dp(s, e, rem):
			if rem < 0 or abs(locations[s] - locations[e]) > rem:
				return 0
			if s == e and rem == 0:
				return 1
			re = 0 if s != e else 1
			for i in range(lc):
				if i != s:
					used = abs(locations[s] - locations[i])
					re += rec_dp(i, e, rem - used)
			return re % mod
		return rec_dp(start, finish, fuel)


from functools import lru_cache
MODULO = 10 ** 9 + 7

class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:

		@lru_cache(maxsize=None)
		def dp(start_pos, fuel_remaining):
			if fuel_remaining < 0:
				return 0
			ways = 1 if start_pos == finish else 0
			if fuel_remaining == 0:
				return ways
			for i in range(len(locations)):
				if i == start_pos:
					continue
				fuel_wasted = abs(locations[i] - locations[start_pos])
				ways = (ways + dp(i, fuel_remaining - fuel_wasted)) % MODULO
			return ways
		return dp(start, fuel)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		MOD = pow(10, 9) + 7
		N = len(locations)

		@lru_cache(None)
		def dfs(cur, fuel):
			if fuel < 0:
				return 0
			ans = 0
			if cur == finish:
				ans += 1
			for (i, loc) in enumerate(locations):
				if i == cur:
					continue
				if fuel >= abs(locations[i] - locations[cur]):
					ans += dfs(i, fuel - abs(locations[i] - locations[cur])) % MOD
					ans %= MOD
			ans %= MOD
			return ans
		return dfs(start, fuel)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		dic = []
		n = len(locations)
		for i in range(n):
			dic.append([None] * (fuel + 1))

		def dp(l, s, f, fuel, dic, n):
			if fuel == 0:
				if s == f:
					return 1
				return 0
			if dic[s][fuel] != None:
				return dic[s][fuel]
			number = 0
			if s == f:
				number = 1
			for i in range(n):
				if i != s:
					if abs(l[i] - l[s]) <= fuel:
						number += dp(l, i, f, fuel - abs(l[i] - l[s]), dic, n)
			dic[s][fuel] = number
			return number
		return dp(locations, start, finish, fuel, dic, n) % 1000000007


from functools import lru_cache

class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:

		@lru_cache(None)
		def h(start, finish, fuel):
			if fuel < 0:
				return 0
			res = start == finish
			for i in range(len(locations)):
				if i != start:
					res += h(i, finish, fuel - abs(locations[i] - locations[start]))
			return res
		return h(start, finish, fuel) % (10 ** 9 + 7)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		n = len(locations)
		mod = 10 ** 9 + 7
		dp = [[-1] * (fuel + 1) for _ in range(n)]

		def dfs(s, remain):
			if remain < 0:
				return 0
			if dp[s][remain] != -1:
				return dp[s][remain]
			res = 0
			if s == finish:
				res += 1
			for i in range(n):
				if i != s:
					res += dfs(i, remain - abs(locations[i] - locations[s]))
			dp[s][remain] = res
			return res
		return dfs(start, fuel) % mod


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		DP = [[-1] * len(locations) for _ in range(fuel + 1)]
		ans = self.dfs(locations, start, finish, fuel, DP, start) % (10 ** 9 + 7)
		return ans

	def dfs(self, locations, start, finish, fuel, DP, cur):
		paths = 0
		if cur == finish and fuel >= 0:
			paths += 1
		for i in range(len(locations)):
			if i == cur:
				continue
			if fuel - abs(locations[i] - locations[cur]) < 0:
				continue
			if DP[fuel - abs(locations[i] - locations[cur])][i] == -1:
				DP[fuel - abs(locations[i] - locations[cur])][i] = self.dfs(locations, start, finish, fuel - abs(locations[i] - locations[cur]), DP, i)
			paths += DP[fuel - abs(locations[i] - locations[cur])][i]
		return paths


from functools import lru_cache

class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:

		@lru_cache(None)
		def dp(cur, fuel):
			res = int(cur == finish)
			for i in range(cur - 1, -1, -1):
				if locations[cur] - locations[i] > fuel:
					break
				res += dp(i, fuel - (locations[cur] - locations[i]))
			for i in range(cur + 1, len(locations)):
				if locations[i] - locations[cur] > fuel:
					break
				res += dp(i, fuel - (locations[i] - locations[cur]))
			return res % MOD
		MOD = 10 ** 9 + 7
		(start_loc, finish_loc) = (locations[start], locations[finish])
		locations.sort()
		start = locations.index(start_loc)
		finish = locations.index(finish_loc)
		return dp(start, fuel)


class Solution:

	def countRoutes(self, A: List[int], start: int, finish: int, fuel: int) -> int:
		mod = 10 ** 9 + 7
		d = {}
		t = {}
		for (i, ele) in enumerate(A):
			d[i] = ele
			t[ele] = i
		nums = sorted(A)

		@lru_cache(None)
		def dp(i, j, f):
			if not f:
				return i == j
			loc = d[i]
			(l, r) = (bisect.bisect_left(nums, loc - f), bisect.bisect_right(nums, loc + f))
			res = 1 if i == j else 0
			for ele in nums[l:r]:
				if ele != loc:
					res += dp(t[ele], j, f - abs(ele - loc)) % mod
			return res
		return dp(start, finish, fuel) % mod


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		m = 10 ** 9 + 7
		n = len(locations)
		dp = [[-1 for _ in range(fuel + 1)] for _ in range(n)]
		return self.helper(locations, start, finish, dp, fuel)

	def helper(self, locations, curr, end, dp, fuel):
		if fuel < 0:
			return 0
		if dp[curr][fuel] != -1:
			return dp[curr][fuel]
		if curr == end:
			res = 1
		else:
			res = 0
		for nxt in range(len(locations)):
			if nxt != curr:
				res += self.helper(locations, nxt, end, dp, fuel - abs(locations[curr] - locations[nxt]))
		dp[curr][fuel] = res % (10 ** 9 + 7)
		return dp[curr][fuel]


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		mod = 10 ** 9 + 7
		memo = {}

		def solve(pos, fuel):
			if fuel == 0:
				return pos == finish
			elif (pos, fuel) in memo:
				return memo[pos, fuel]
			ret = pos == finish
			for i in range(len(locations)):
				if i != pos:
					cost = abs(locations[i] - locations[pos])
					if cost <= fuel:
						ret += solve(i, fuel - cost) % mod
			memo[pos, fuel] = ret % mod
			return ret % mod
		return solve(start, fuel)


class Solution:

	def countRoutes(self, A: List[int], start: int, finish: int, fuel: int) -> int:
		MOD = 10 ** 9 + 7

		@functools.lru_cache(None)
		def f(i, fu):
			res = int(i == finish)
			for (j, p) in enumerate(A):
				d = abs(p - A[i])
				if j != i and d <= fu:
					res = (res + f(j, fu - d)) % MOD
			return res
		return f(start, fuel) % MOD


from typing import List
import functools

class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		MOD = 10 ** 9 + 7

		@functools.lru_cache(None)
		def foo(loc, f):
			print(loc, f)
			res = 1 if loc == finish else 0
			for i in range(len(locations)):
				if i != loc:
					temp = f - abs(locations[loc] - locations[i])
					if temp >= 0:
						res = (res + foo(i, temp)) % MOD
			return res % MOD
		return foo(start, fuel)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		ref = defaultdict(list)
		from functools import lru_cache
		finish = locations[finish]
		MOD = 10 ** 9 + 7
		mycache = {}

		def solve(pos, rfuel):
			if (pos, rfuel) in mycache:
				return mycache[pos, rfuel]
			sol = 0
			if pos == finish:
				sol += 1
			for it in locations:
				if it == pos:
					continue
				tup = (it, abs(pos - it))
				if tup[1] <= rfuel:
					sol += solve(tup[0], rfuel - tup[1])
			mycache[pos, rfuel] = sol % MOD
			return sol
		solve(locations[start], fuel)
		return mycache[locations[start], fuel] % MOD


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		n = len(locations)
		DP = [[-1 for j in range(fuel + 1)] for j in range(n)]
		return self.helper(locations, start, finish, DP, fuel) % (10 ** 9 + 7)

	def helper(self, locations, curr, end, DP, fuel):
		if fuel < 0:
			return 0
		if DP[curr][fuel] != -1:
			return DP[curr][fuel]
		ans = 1 if curr == end else 0
		for next_ in range(len(locations)):
			if next_ != curr:
				ans += self.helper(locations, next_, end, DP, fuel - abs(locations[next_] - locations[curr]))
		DP[curr][fuel] = ans
		return ans


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		MOD = 10 ** 9 + 7
		N = len(locations)

		@lru_cache(None)
		def dp(curr, fuelLeft):
			ans = int(curr == finish)
			for nxt in range(N):
				if nxt != curr:
					f = abs(locations[nxt] - locations[curr])
					if f <= fuelLeft:
						ans = (ans + dp(nxt, fuelLeft - f)) % MOD
			return ans
		return dp(start, fuel)


def count_all_possible_routes(locations, start, finish, fuel):
	loc_count = len(locations)
	dp_store = [[-1] * (fuel + 1) for loc in range(loc_count)]

	def count_all_possible_routes_recur(curr_loc, rem_fuel):
		if rem_fuel < 0:
			return 0
		if dp_store[curr_loc][rem_fuel] > -1:
			return dp_store[curr_loc][rem_fuel]
		ans = 0
		if curr_loc == finish:
			ans += 1
		for (city, pos) in enumerate(locations):
			if city == curr_loc:
				continue
			ans += count_all_possible_routes_recur(city, rem_fuel - abs(pos - locations[curr_loc]))
		dp_store[curr_loc][rem_fuel] = ans
		return ans
	return count_all_possible_routes_recur(start, fuel) % (10 ** 9 + 7)

class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		return count_all_possible_routes(locations, start, finish, fuel)


from functools import lru_cache
from collections import defaultdict

class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		cost = defaultdict(list)
		for (i, c1) in enumerate(locations):
			for c2 in locations:
				cost[i].append(abs(c1 - c2))

		@lru_cache(None)
		def dp(position, f):
			ret = 0 if position != finish else 1
			for (dst, c) in enumerate(cost[position]):
				if f >= c and dst != position:
					ret = (ret + dp(dst, f - c)) % 1000000007
			return ret
		return dp(start, fuel)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		fuelReduce = lambda x, y: abs(x - y)

		@lru_cache(None)
		def dfs(city, fuel):
			if fuel < 0:
				return 0
			ans = 0
			if city == finish:
				ans = ans + 1
			for next in range(len(locations)):
				if city != next:
					ans = ans + dfs(next, fuel - fuelReduce(locations[city], locations[next]))
			return ans
		return dfs(start, fuel) % (10 ** 9 + 7)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:

		def getLocations(location, fuel):
			if (location, fuel) in mem:
				return mem[location, fuel]
			if fuel < 0:
				return 0
			ans = 0
			if location == locations[finish]:
				ans = 1
			for newLoc in locations:
				if newLoc != location:
					ans += getLocations(newLoc, fuel - abs(location - newLoc))
			mem[location, fuel] = ans
			return ans
		mem = {}
		return getLocations(locations[start], fuel) % (10 ** 9 + 7)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		self.N = len(locations)
		self.finish = finish
		self.M = dict()

		def dfs(i, f):
			if (i, f) not in self.M:
				res = 0
				if i == self.finish:
					res += 1
				for j in range(self.N):
					if j != i and f >= abs(locations[i] - locations[j]) + abs(locations[finish] - locations[j]):
						res += dfs(j, f - abs(locations[i] - locations[j]))
				self.M[i, f] = res
			return self.M[i, f]
		return dfs(start, fuel) % (10 ** 9 + 7)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		mem = {}
		MOD = 10 ** 9 + 7

		def dp(i, gas):
			if gas < 0:
				return 0
			if (i, gas) in mem:
				return mem[i, gas]
			res = 0
			if i == finish:
				res += 1
			for j in range(len(locations)):
				dist = abs(locations[j] - locations[i])
				if i == j or dist > gas:
					continue
				res += dp(j, gas - dist)
			mem[i, gas] = res % MOD
			return res
		return dp(start, fuel) % MOD


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		cost = lambda i, j: abs(locations[i] - locations[j])

		@lru_cache(maxsize=None)
		def dfs(i, f):
			if f < 0:
				return 0
			total = 0
			if i == finish:
				total += 1
			for j in range(len(locations)):
				if i == j:
					continue
				total += dfs(j, f - cost(i, j))
			return total
		return dfs(start, fuel) % (10 ** 9 + 7)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		n = len(locations)
		dp = [[-1] * (fuel + 1) for _ in range(n)]
		return self.dfs(start, finish, fuel, dp, locations)

	def dfs(self, start, finish, fuel, dp, locations):
		if fuel < 0:
			return 0
		if dp[start][fuel] > -1:
			return dp[start][fuel]
		if start == finish:
			res = 1
		else:
			res = 0
		n = len(locations)
		for i in range(n):
			if i == start:
				continue
			else:
				res = res + self.dfs(i, finish, fuel - abs(locations[i] - locations[start]), dp, locations)
		dp[start][fuel] = res % (1000000000 + 7)
		return dp[start][fuel]


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		dp = [[-1] * 201 for _ in range(101)]
		MOD = 1000000007

		def helper(pos, left):
			if left < 0:
				return 0
			if dp[pos][left] != -1:
				return dp[pos][left]
			ans = 1 if pos == finish else 0
			for (i, loc) in enumerate(locations):
				if i != pos and left - abs(loc - locations[pos]) >= 0:
					ans += helper(i, left - abs(loc - locations[pos]))
			ans %= MOD
			dp[pos][left] = ans
			return ans
		return helper(start, fuel)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		MOD = 10 ** 9 + 7
		(start, finish) = (locations[start], locations[finish])
		locations.sort()
		(start, finish) = (locations.index(start), locations.index(finish))
		n = len(locations)

		@lru_cache(None)
		def dp(i, f):
			res = 0
			if i == finish:
				res = 1
			if f == 0:
				return res
			for j in range(1, i + 1):
				ff = locations[i] - locations[i - j]
				if ff <= f:
					res = (res + dp(i - j, f - ff)) % MOD
				else:
					break
			for j in range(1, n - i):
				ff = locations[i + j] - locations[i]
				if ff <= f:
					res = (res + dp(i + j, f - ff)) % MOD
				else:
					break
			return res
		return dp(start, fuel)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:

		def cost(i, j):
			return abs(locations[i] - locations[j])
		(n, MOD) = (len(locations), 10 ** 9 + 7)

		@functools.lru_cache(None)
		def solve(s, fuel):
			if fuel < 0:
				return 0
			ans = 1 if s == finish else 0
			for t in range(n):
				if s == t:
					continue
				ans += solve(t, fuel - cost(s, t))
			return ans % MOD
		return solve(start, fuel)


from collections import deque

class Solution:

	def rec(self, curr, finish, fuel_left, dp, locations, p):
		cnt = 0
		if curr == finish:
			cnt = 1
		n = len(locations)
		for i in range(n):
			if i != curr and fuel_left - abs(locations[i] - locations[curr]) >= 0:
				if dp[fuel_left - abs(locations[i] - locations[curr])][i] != -1:
					cnt = (cnt + dp[fuel_left - abs(locations[i] - locations[curr])][i]) % p
				else:
					cnt = (cnt + self.rec(i, finish, fuel_left - abs(locations[i] - locations[curr]), dp, locations, p)) % p
		dp[fuel_left][curr] = cnt % p
		return cnt % p

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		n = len(locations)
		p = 1000000007
		dp = [[-1 for i in range(n)] for j in range(fuel + 1)]
		return self.rec(start, finish, fuel, dp, locations, p)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		cost = lambda i, j: abs(locations[i] - locations[j])

		@lru_cache(None)
		def dfs(cur, remain_fuel):
			if remain_fuel < 0:
				return 0
			return sum((dfs(next_city, remain_fuel - cost(cur, next_city)) for next_city in range(len(locations)) if cur != next_city)) + (cur == finish)
		constant = 10 ** 9 + 7
		return dfs(cur=start, remain_fuel=fuel) % constant


class Solution:

	def countRoutes(self, L: List[int], start: int, finish: int, fuel: int) -> int:
		cost = lambda x, y: abs(L[x] - L[y])
		ways = {}

		def numWays(s, f):
			if (s, f) not in ways:
				if f < cost(s, finish):
					return 0
				total = 0
				for u in range(len(L)):
					if u != s:
						total += numWays(u, f - cost(s, u))
				ways[s, f] = total + (s == finish)
			return ways[s, f]
		return numWays(start, fuel) % (10 ** 9 + 7)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:

		def helper(curr, fuelLeft, memo, locations, finish, mod):
			if (curr, fuelLeft) in memo:
				return memo[curr, fuelLeft]
			ret = 0
			if curr == finish:
				ret += 1
			for (i, loc) in enumerate(locations):
				if curr != i:
					candidFuel = fuelLeft - abs(locations[curr] - loc)
					if candidFuel > 0:
						ret = (ret + helper(i, candidFuel, memo, locations, finish, mod)) % mod
					elif candidFuel == 0 and i == finish:
						ret += 1
			memo[curr, fuelLeft] = ret % mod
			return ret
		return helper(start, fuel, {}, locations, finish, 10 ** 9 + 7)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		mod = 10 ** 9 + 7

		@lru_cache(None)
		def count_paths(index, fuel):
			total = 0
			if fuel < 0:
				return 0
			if index == finish:
				total += 1
			current = locations[index]
			for (next_index, x) in enumerate(locations):
				if next_index != index:
					total += count_paths(next_index, max(-1, fuel - abs(current - x)))
			return total
		answer = count_paths(start, fuel)
		return answer % mod


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		x = locations[start]
		y = locations[finish]
		locations.sort()
		u = bisect.bisect_left(locations, x)
		v = bisect.bisect_left(locations, y)
		MOD = int(1000000000.0) + 7

		@lru_cache(None)
		def f(x, left):
			lb = bisect.bisect_left(locations, locations[x] - left)
			rb = bisect.bisect_right(locations, locations[x] + left)
			ret = int(x == v)
			for i in range(lb, rb):
				if i != x:
					ret += f(i, left - abs(locations[i] - locations[x]))
					ret %= MOD
			return ret
		return f(u, fuel)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		mydict = {}

		def func(city, myfuel):
			if myfuel < 0:
				return 0
			if myfuel == 0:
				if city == locations[finish]:
					return 1
				else:
					return 0
			tmp = 0
			for i in locations:
				if i != city:
					if (i, myfuel - abs(i - city)) in mydict:
						tmp += mydict[i, myfuel - abs(i - city)]
					else:
						tmp += func(i, myfuel - abs(i - city))
			if city == locations[finish]:
				tmp = tmp + 1
			mydict[city, myfuel] = tmp
			return tmp
		count = func(locations[start], fuel)
		return count % (10 ** 9 + 7)


class Solution:

	def search(self, locations, start, finish, fuel):
		if (start, fuel) in self.memo:
			return self.memo[start, fuel]
		count = 0
		if start == finish:
			count += 1
		for (i, loc) in enumerate(locations):
			dist = abs(locations[start] - loc)
			if i == start or dist > fuel:
				continue
			count += self.search(locations, i, finish, fuel - dist)
		self.memo[start, fuel] = count % (10 ** 9 + 7)
		return self.memo[start, fuel]

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		self.memo = {}
		return self.search(locations, start, finish, fuel)


MOD = 10 ** 9 + 7

class Solution:

	def countRoutes(self, A: List[int], start: int, finish: int, fuel: int) -> int:
		n = len(A)

		@lru_cache(None)
		def dfs(i, k):
			res = int(i == finish)
			for j in range(n):
				if i == j:
					continue
				if abs(A[i] - A[j]) > k:
					continue
				res += dfs(j, k - abs(A[i] - A[j]))
				res %= MOD
			return res
		return dfs(start, fuel)


MOD = int(1000000000.0 + 7)

class Solution:

	def num_routes(self, start, finish, fuel):
		min_fuel = abs(self.loc[start] - self.loc[finish])
		if fuel < min_fuel:
			return 0
		if fuel == 0:
			return 1 if start == finish else 0
		try:
			return self.cache[start, finish, fuel]
		except KeyError:
			ret = 1 if start == finish else 0
			for first_stop in range(len(self.loc)):
				if first_stop == start:
					continue
				first_fuel = abs(self.loc[start] - self.loc[first_stop])
				if fuel < first_fuel:
					continue
				ret = (ret + self.num_routes(first_stop, finish, fuel - first_fuel)) % MOD
			self.cache[start, finish, fuel] = ret
			return ret

	def countRoutes(self, locations, start, finish, fuel):
		self.loc = locations
		self.cache = {}
		return self.num_routes(start, finish, fuel)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		dp = [[-1 for i in range(len(locations))] for j in range(fuel + 1)]
		out = self.helper(locations, start, finish, fuel, dp, start)
		return out % 1000000007

	def helper(self, locations, start, finish, fuel, dp, index):
		if fuel < 0:
			return 0
		if dp[fuel][index] != -1:
			return dp[fuel][index]
		if index == finish:
			ans = 1
			for i in range(len(locations)):
				if i != index:
					ans += self.helper(locations, start, finish, fuel - abs(locations[i] - locations[index]), dp, i)
		else:
			ans = 0
			for i in range(len(locations)):
				if i != index:
					ans += self.helper(locations, start, finish, fuel - abs(locations[i] - locations[index]), dp, i)
		dp[fuel][index] = ans
		return ans


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:

		def dfs(i, fuel):
			if fuel < 0:
				return 0
			elif fuel == 0:
				return 1 if i == finish else 0
			if (i, fuel) not in cache:
				cnt = 1 if i == finish else 0
				for (j, cost) in enumerate(locations):
					if j == i:
						continue
					remain = fuel - abs(cost - locations[i])
					if remain >= 0:
						cnt += dfs(j, remain)
				cache[i, fuel] = cnt
			return cache[i, fuel]
		cache = dict()
		return dfs(start, fuel) % (10 ** 9 + 7)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		n = len(locations)
		dp = [[-1] * (fuel + 1) for _ in range(n)]

		def solve(current, fuel):
			if fuel < 0:
				return 0
			if dp[current][fuel] != -1:
				return dp[current][fuel]
			ans = 1 if current == finish else 0
			for next in range(n):
				if next != current:
					ans = (ans + solve(next, fuel - abs(locations[current] - locations[next]))) % 1000000007
			dp[current][fuel] = ans
			return ans
		return solve(start, fuel)


def neigh(start, locations, fuel):
	res = []
	n = len(locations)
	for j in range(n):
		i = locations[j]
		if j == start:
			continue
		if abs(i - locations[start]) <= fuel:
			res.append(j)
	return res

class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		if abs(locations[finish] - locations[start]) > fuel:
			return 0
		n = len(locations)
		dp = [[-1 for i in range(fuel + 1)] for j in range(n)]

		def dfs(start, fuel):
			if fuel < 0:
				return 0
			if dp[start][fuel] != -1:
				return dp[start][fuel]
			neighs = neigh(start, locations, fuel)
			count = 0
			if start == finish:
				count += 1
			for i in neighs:
				count += dfs(i, fuel - abs(locations[start] - locations[i]))
			dp[start][fuel] = count
			return count
		return dfs(start, fuel) % (pow(10, 9) + 7)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		cost = lambda a, b: abs(locations[a] - locations[b])
		N = len(locations)

		@lru_cache(None)
		def dfs(curr, fuel):
			if fuel < 0:
				return 0
			ans = 1 if curr == finish else 0
			return ans + sum((dfs(i, fuel - cost(curr, i)) for i in range(N) if i != curr))
		return dfs(start, fuel) % (10 ** 9 + 7)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:

		@lru_cache(None)
		def dfs(start, finish, fuel):
			if abs(locations[start] - locations[finish]) > fuel:
				return 0
			res = 1 if start == finish else 0
			for (i, v) in enumerate(locations):
				if i == start:
					continue
				res += dfs(i, finish, fuel - abs(v - locations[start]))
			return res
		mod = 10 ** 9 + 7
		return dfs(start, finish, fuel) % mod


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		m = {}
		for (i, loc) in enumerate(locations):
			m[loc] = i
		dp = [[0 for _ in range(len(locations))] for _ in range(fuel + 1)]
		dp[fuel][start] = 1
		for f in range(fuel, -1, -1):
			for (i, c) in enumerate(dp[f]):
				if c > 0:
					for (j, loc) in enumerate(locations):
						if i != j and abs(locations[i] - loc) <= f:
							dp[f - abs(locations[i] - loc)][j] += c
		return sum([dp[i][finish] for i in range(fuel + 1)]) % (10 ** 9 + 7)


import sys
sys.setrecursionlimit(10 ** 9)

class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		M = 10 ** 9 + 7

		@lru_cache(None)
		def helper(curr_city, curr_fuel):
			if curr_fuel < 0:
				return 0
			ans = 0
			if curr_city == finish:
				ans += 1
			for i in range(len(locations)):
				if i != curr_city:
					ans += helper(i, curr_fuel - abs(locations[i] - locations[curr_city]))
					ans %= M
			return ans
		return helper(start, fuel)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		dp = [[-1 for i in range(fuel + 1)] for j in range(len(locations))]
		for i in range(len(locations)):
			if i == finish:
				dp[i][0] = 1
			else:
				dp[i][0] = 0
		self.dfs(locations, start, fuel, finish, dp)
		return dp[start][fuel] % (10 ** 9 + 7)

	def dfs(self, locations, loc, fuel, finish, dp):
		if dp[loc][fuel] != -1:
			return
		if loc == finish:
			dp[loc][fuel] = 1
		else:
			dp[loc][fuel] = 0
		for next_loc in range(len(locations)):
			if next_loc == loc:
				continue
			if fuel >= abs(locations[loc] - locations[next_loc]):
				fuel_res = fuel - abs(locations[loc] - locations[next_loc])
				self.dfs(locations, next_loc, fuel_res, finish, dp)
				dp[loc][fuel] += dp[next_loc][fuel_res]


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		mod = 10 ** 9 + 7

		def dfs(cur, dp, f):
			if f < 0:
				return 0
			if dp[cur][f] != -1:
				return dp[cur][f]
			route = 0
			if cur == finish:
				route = 1
			for j in range(len(locations)):
				if cur != j:
					route = (route + dfs(j, dp, f - abs(locations[cur] - locations[j]))) % mod
			dp[cur][f] = route
			return route
		dp = [[-1 for _ in range(fuel + 1)] for _ in range(len(locations))]
		return dfs(start, dp, fuel)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		n = len(locations)
		cache = {}

		def process(start, fuel):
			if not (start, fuel) in cache:
				ans = 0
				if fuel == 0:
					ans = 1 if start == finish else 0
				else:
					if start == finish:
						ans += 1
					for i in range(n):
						if i != start and abs(locations[i] - locations[start]) <= fuel:
							ans += process(i, fuel - abs(locations[i] - locations[start]))
				cache[start, fuel] = ans % (10 ** 9 + 7)
			return cache[start, fuel]
		return process(start, fuel)


class Solution1:

	def helper(self, cur_loc, fuel):
		print(cur_loc, fuel)
		if (cur_loc, fuel) in self.mem:
			return self.mem[cur_loc, fuel]
		if fuel <= 0:
			return 0
		if cur_loc == self.finish and fuel == 0:
			return 1
		ans = 0
		for loc in self.locations:
			if loc != cur_loc:
				ans += self.helper(loc, fuel - abs())
		ans = ans % (10 ** 9 + 7)
		self.mem[cur_loc, fuel] = ans
		return ans

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		self.finish = finish
		self.locations = locations
		self.mem = {}
		ans = self.helper(start, fuel)
		return ans

class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		cost = lambda i, j: abs(locations[i] - locations[j])

		@lru_cache(None)
		def dfs(cur, remain_fuel):
			if remain_fuel < 0:
				return 0
			return sum((dfs(next_city, remain_fuel - cost(cur, next_city)) for next_city in range(len(locations)) if cur != next_city)) + (cur == finish)
		constant = 10 ** 9 + 7
		return dfs(cur=start, remain_fuel=fuel) % constant


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		mem = {}

		def dfs(idx, currFuel):
			key = (idx, currFuel)
			if key in mem:
				return mem[key]
			if currFuel < 0:
				return 0
			res = 1 if idx == finish else 0
			for i in range(len(locations)):
				if i != idx:
					res += dfs(i, currFuel - abs(locations[idx] - locations[i]))
			mem[key] = res
			return mem[key]
		return dfs(start, fuel) % (10 ** 9 + 7)


class Solution:

	def dfs(self, cur, end, dp, locations, fuel):
		if fuel < 0:
			return 0
		if dp[cur][fuel] != -1:
			return dp[cur][fuel]
		if cur == end:
			ans = 1
		else:
			ans = 0
		for next_city in range(len(locations)):
			if next_city != cur:
				ans = (ans + self.dfs(next_city, end, dp, locations, fuel - abs(locations[next_city] - locations[cur]))) % 1000000007
		dp[cur][fuel] = ans
		return ans

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		n = len(locations)
		dp = [[-1 for _ in range(fuel + 1)] for _ in range(n)]
		return self.dfs(start, finish, dp, locations, fuel)


from functools import lru_cache

class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		(s, f) = (locations[start], locations[finish])
		locations.sort()
		maps = {}
		for (i, loc) in enumerate(locations):
			maps[loc] = i

		@lru_cache(maxsize=None)
		def helper(l, r, fuel):
			if l == r:
				count = 1
				for loc in locations:
					if loc != l and abs(loc - l) + abs(loc - r) <= fuel:
						n1 = 1
						n2 = helper(loc, r, fuel - abs(loc - l))
						count += n2
				return count
			if abs(r - l) > fuel:
				return 0
			else:
				count = 0
				for loc in locations:
					if loc != l and abs(loc - l) + abs(loc - r) <= fuel:
						n1 = 1
						n2 = helper(loc, r, fuel - abs(loc - l))
						count += n2
				return count
		return helper(s, f, fuel) % (10 ** 9 + 7)


class Solution:

	def countRoutes(self, A: List[int], start: int, end: int, fuel: int) -> int:
		mod = 10 ** 9 + 7
		cost = lambda a, b: abs(A[a] - A[b])

		@functools.lru_cache(None)
		def route(start, fuel):
			nonlocal end
			if fuel < 0:
				return 0
			r = 1 if start == end else 0
			for i in range(len(A)):
				if i == start:
					continue
				r += route(i, fuel - cost(start, i)) % mod
			return r % mod
		answer = route(start, fuel)
		return answer


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		memo = {}

		def f(i, fuel_remain):
			if (i, fuel_remain) in memo:
				return memo[i, fuel_remain]
			total = 0
			for j in range(len(locations)):
				if i == j or abs(locations[j] - locations[i]) > fuel_remain:
					continue
				if j == finish:
					total += 1
				total += f(j, fuel_remain - abs(locations[j] - locations[i]))
			memo[i, fuel_remain] = total
			return total % (10 ** 9 + 7)
		return f(start, fuel) + (1 if start == finish else 0)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:

		def help(locations, cur, e, dp, fuel):
			if fuel < 0:
				return 0
			if dp[cur][fuel] != -1:
				return dp[cur][fuel]
			ans = 1 if cur == e else 0
			for next in range(len(locations)):
				if next != cur:
					ans = (ans + help(locations, next, e, dp, fuel - abs(locations[cur] - locations[next]))) % 1000000007
			dp[cur][fuel] = ans
			return ans
		n = len(locations)
		dp = [[-1] * (fuel + 1) for _ in range(n)]
		return help(locations, start, finish, dp, fuel)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:

		@lru_cache(maxsize=None)
		def traverse(curr: int, fuel: int) -> int:
			if fuel < 0:
				return 0
			res = 0
			if curr == finish:
				res += 1
				if fuel == 0:
					return res
			for (i, location) in enumerate(locations):
				if i != curr:
					res += traverse(i, fuel - abs(location - locations[curr]))
			return res
		return traverse(start, fuel) % (10 ** 9 + 7)


def solve(locations, curr, end, dp, fuel):
	if fuel < 0:
		return 0
	if dp[curr][fuel] != -1:
		return dp[curr][fuel]
	if curr == end:
		ans = 1
	else:
		ans = 0
	for j in range(len(locations)):
		if j != curr:
			ans = (ans + solve(locations, j, end, dp, fuel - abs(locations[j] - locations[curr]))) % 1000000007
	dp[curr][fuel] = ans
	return dp[curr][fuel]

class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		dp = [[-1 for i in range(fuel + 1)] for j in range(len(locations))]
		return solve(locations, start, finish, dp, fuel)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		n = len(locations)
		dp = [[-1] * (fuel + 1) for _ in range(n)]
		ans = self.dfs(locations, start, finish, fuel, dp)
		return ans

	def dfs(self, location, curr_city, finish, fuel, dp):
		if fuel < 0:
			return 0
		if dp[curr_city][fuel] != -1:
			return dp[curr_city][fuel]
		ans = 0
		if curr_city == finish:
			ans = 1
		for next_city in range(len(location)):
			if next_city == curr_city:
				continue
			else:
				ans = ans + self.dfs(location, next_city, finish, fuel - abs(location[curr_city] - location[next_city]), dp)
				ans %= 1000000007
		dp[curr_city][fuel] = ans
		return ans


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:

		@lru_cache(None)
		def dp(i, left):
			if left < 0:
				return 0
			ret = i == finish
			for ni in range(len(locations)):
				if i == ni:
					continue
				ret += dp(ni, left - abs(locations[i] - locations[ni]))
			return ret
		return dp(start, fuel) % (10 ** 9 + 7)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		cost = lambda i, j: abs(locations[i] - locations[j])

		@lru_cache(None)
		def dfs(i, f):
			if f < 0:
				return 0
			return sum([dfs(j, f - cost(i, j)) for j in range(len(locations)) if j != i]) + (i == finish)
		return dfs(start, fuel) % (10 ** 9 + 7)

	def countRoutes1(self, L: List[int], st: int, end: int, f: int) -> int:
		M = 10 ** 9 + 7
		res = 0

		def dfs(st, end, f):
			for (i, c) in enumerate(L):
				need = abs(c - L[st])
				if need <= f:
					if i == end:
						res += 1
					elif need < f:
						dfs(i, end, f - need)
		dfs(st, end, f)
		return res % M


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:

		@lru_cache(None)
		def dfs(current, fuel):
			ans = 0
			if fuel >= 0:
				if current == finish:
					ans += 1
				for (i, loc) in enumerate(locations):
					if i != current:
						consume = abs(locations[current] - loc)
						ans += dfs(i, fuel - consume)
			return ans % (10 ** 9 + 7)
		ret = dfs(start, fuel)
		return ret


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		n = len(locations)
		dp = [[-1 for _ in range(fuel)] for _ in range(n)]
		r = self.helper(locations, start, dp, fuel, finish)
		print(dp)
		return r

	def helper(self, locations, cur, dp, fuel, ed):
		if fuel < 0:
			return 0
		if dp[cur][fuel - 1] != -1:
			return dp[cur][fuel - 1]
		n = len(locations)
		r = 0
		if cur == ed:
			r += 1
		for i in range(n):
			if i != cur:
				r += self.helper(locations, i, dp, fuel - abs(locations[cur] - locations[i]), ed)
		dp[cur][fuel - 1] = r % (10 ** 9 + 7)
		return dp[cur][fuel - 1]


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		numCity = len(locations)
		dp = [[None] * numCity for _ in range(fuel + 1)]

		def helper(city, fuel):
			if fuel < 0:
				return 0
			res = dp[fuel][city]
			if res is not None:
				return res
			res = (int(city == finish) + sum((helper(city2, fuel - abs(locations[city] - locations[city2])) for city2 in range(numCity) if city != city2))) % (10 ** 9 + 7)
			dp[fuel][city] = res
			return res
		return helper(start, fuel)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		locLen = len(locations)
		MOD = 10 ** 9 + 7
		dp = {}

		def helper(i, f):
			if (i, f) in dp:
				return dp[i, f]
			subAns = 0
			for i1 in range(locLen):
				if i1 == i or abs(locations[i1] - locations[i]) > f:
					continue
				if i1 == finish:
					subAns += 1 + helper(i1, f - abs(locations[i1] - locations[i]))
				else:
					subAns += helper(i1, f - abs(locations[i1] - locations[i]))
			dp[i, f] = subAns % MOD
			return dp[i, f]
		return helper(start, fuel) + (1 if start == finish else 0)


class Solution:

	def dp(self, A, curr, e, fuel, dp):
		mod = 10 ** 9 + 7
		if fuel < 0:
			return 0
		if dp[curr][fuel] != -1:
			return dp[curr][fuel]
		ans = 1 if curr == e else 0
		for nxt in range(len(A)):
			if nxt != curr:
				ans += self.dp(A, nxt, e, fuel - abs(A[curr] - A[nxt]), dp)
				ans %= mod
		dp[curr][fuel] = ans
		return ans

	def countRoutes(self, A: List[int], s: int, e: int, fuel: int) -> int:
		if not A:
			return 0
		n = len(A)
		dp = [[-1] * (fuel + 1) for _ in range(n)]
		return self.dp(A, s, e, fuel, dp)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		MOD = 10 ** 9 + 7
		pos_start = locations[start]
		pos_finish = locations[finish]
		locations.sort()
		start = locations.index(pos_start)
		finish = locations.index(pos_finish)

		@lru_cache(maxsize=None)
		def find(start, fuel):
			count = 0
			if abs(start - finish) == 1 and fuel == abs(locations[start] - locations[finish]):
				return 1
			if locations[start] == locations[finish]:
				count += 1
			if fuel >= abs(locations[start] - locations[finish]):
				for i in range(start - 1, -1, -1):
					if abs(locations[start] - locations[i]) + abs(locations[i] - locations[finish]) <= fuel:
						count += find(i, fuel - abs(locations[start] - locations[i]))
					else:
						break
				for j in range(start + 1, len(locations)):
					if abs(locations[start] - locations[j]) + abs(locations[j] - locations[finish]) <= fuel:
						count += find(j, fuel - abs(locations[start] - locations[j]))
					else:
						break
			return count
		return find(start, fuel) % MOD


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		self.res = 0
		memo = {}

		def dfs(cur_city, fuel):
			if (cur_city, fuel) in memo:
				return memo[cur_city, fuel]
			if fuel < 0:
				return 0
			cnt = 0
			if cur_city == finish:
				cnt = 1
			for i in range(len(locations)):
				if i == cur_city:
					continue
				cnt += dfs(i, fuel - abs(locations[i] - locations[cur_city]))
			memo[cur_city, fuel] = cnt
			return cnt
		return dfs(start, fuel) % (10 ** 9 + 7)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		n = len(locations)
		dp = [[-1] * (fuel + 1) for i in range(n)]
		mod = 10 ** 9 + 7

		def dfs(cur, fin, fu):
			if fu < 0:
				return 0
			if dp[cur][fu] != -1:
				return dp[cur][fu] % mod
			if cur == fin:
				ans = 1
			else:
				ans = 0
			for i in range(n):
				if i != cur:
					ans = ans + dfs(i, fin, fu - abs(locations[i] - locations[cur])) % mod
			dp[cur][fu] = ans % mod
			return ans % mod
		return dfs(start, finish, fuel) % mod


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		mod = 10 ** 9 + 7

		@lru_cache(None)
		def func(a, fuel):
			t = 0
			if fuel < 0:
				return 0
			if a == finish:
				t += 1
			curr = locations[a]
			for (i, item) in enumerate(locations):
				if i != a:
					t += func(i, max(-1, fuel - abs(curr - item)))
					t %= mod
			return t % mod
		c = func(start, fuel)
		return c % mod


from functools import lru_cache

class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		MOD = 10 ** 9 + 7

		@lru_cache(None)
		def dp(pos, f):
			nonlocal finish
			nonlocal MOD
			res = 0
			if f < 0:
				return 0
			if pos == finish:
				res += 1
			if f == 0:
				return res
			for (i, vi) in enumerate(locations):
				if i == pos:
					continue
				res += dp(i, f - abs(locations[pos] - vi))
			return res % MOD
		ans = dp(start, fuel)
		return ans % MOD


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		mod = 10 ** 9 + 7

		def dfs(cur_loc, fuel):
			if (cur_loc, fuel) in mem:
				return mem[cur_loc, fuel]
			if fuel < 0:
				return 0
			ans = 0
			if cur_loc == finish:
				ans = 1
			for i in range(len(locations)):
				if cur_loc == i:
					continue
				ans += dfs(i, fuel - abs(locations[cur_loc] - locations[i]))
			mem[cur_loc, fuel] = ans
			return ans
		mem = {}
		return dfs(start, fuel) % mod


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		MOD = 10 ** 9 + 7
		n = len(locations)
		from functools import lru_cache

		@lru_cache(None)
		def ways(index, remFuel):
			if index == finish:
				ans = 1
				possible = True
			else:
				ans = 0
				possible = False
			for i in range(n):
				if i == index:
					continue
				dist = abs(locations[i] - locations[index])
				if dist <= remFuel:
					possible = True
					w = ways(i, remFuel - dist)
					ans = (ans + w) % MOD
			if possible:
				return ans
			return 0
		return ways(start, fuel) % MOD


class Solution:

	def countRoutes(self, nums: List[int], start: int, finish: int, fuel: int) -> int:

		def dp(i, f, cache):
			if f < 0:
				return 0
			if f == 0:
				return 1 if i == finish else 0
			if (i, f) not in cache:
				ans = 1 if i == finish else 0
				for j in range(len(nums)):
					if j != i:
						ans += dp(j, f - abs(nums[i] - nums[j]), cache)
				cache[i, f] = ans
			return cache[i, f]
		return dp(start, fuel, {}) % (10 ** 9 + 7)


from collections import deque

class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		N = len(locations)
		M = 10 ** 9 + 7
		adj_matrix = [[0 for _ in range(N)] for _ in range(N)]
		for i in range(N):
			for j in range(i + 1, N):
				adj_matrix[i][j] = abs(locations[i] - locations[j])
				adj_matrix[j][i] = abs(locations[i] - locations[j])
		memo = {}

		def dfs(location, fuel_left):
			if fuel_left < 0:
				return 0
			if (location, fuel_left) in memo:
				return memo[location, fuel_left] % M
			if location == finish:
				cnt = 1
			else:
				cnt = 0
			for dst in range(N):
				if dst == location:
					continue
				if adj_matrix[location][dst] + adj_matrix[dst][finish] <= fuel_left:
					cnt += dfs(dst, fuel_left - adj_matrix[location][dst])
			memo[location, fuel_left] = cnt
			return cnt
		return dfs(start, fuel) % M


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		MOD = 10 ** 9 + 7
		DP = {}

		def f(i, fuel):
			if fuel < 0:
				return 0
			if (i, fuel) in DP:
				return DP[i, fuel]
			count = 0
			if i == finish:
				count += 1
			for j in range(len(locations)):
				if i != j:
					count = (count + f(j, fuel - abs(locations[i] - locations[j]))) % MOD
			DP[i, fuel] = count
			return count
		return f(start, fuel)


class Solution:

	def dfs(self, locations, memo, current, finish, remain_fuel):
		if remain_fuel < 0:
			return 0
		if remain_fuel == 0:
			return 1 if current == finish else 0
		if (current, remain_fuel) in memo:
			return memo[current, remain_fuel]
		l = len(locations)
		ans = 0 if current != finish else 1
		for i in range(l):
			if i == current:
				continue
			dist = abs(locations[current] - locations[i])
			ans += self.dfs(locations, memo, i, finish, remain_fuel - dist)
		memo[current, remain_fuel] = ans
		return ans

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		NUM = 10 ** 9 + 7
		memo = dict()
		return self.dfs(locations, memo, start, finish, fuel) % NUM


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		memo = [[-1 for j in range(fuel + 1)] for i in range(len(locations))]

		def dp(start, fuel):
			nonlocal memo
			nonlocal finish
			nonlocal locations
			if memo[start][fuel] == -1:
				memo[start][fuel] = 1 if start == finish else 0
				for i in range(len(locations)):
					if i != start and fuel >= abs(locations[start] - locations[i]):
						memo[start][fuel] += dp(i, fuel - abs(locations[start] - locations[i]))
						memo[start][fuel] %= 10 ** 9 + 7
			return memo[start][fuel]
		return dp(start, fuel)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		memo = {}
		mod = 10 ** 9 + 7

		def dp(f, c):
			if f == 0 and c == finish:
				return 1
			else:
				if (f, c) not in memo:
					if c == finish and f > 0:
						ans = 1
					else:
						ans = 0
					for nxt in range(len(locations)):
						if nxt == c:
							continue
						dis = abs(locations[c] - locations[nxt])
						if dis <= f:
							ans += dp(f - dis, nxt)
					memo[f, c] = ans % mod
				return memo[f, c]
		return dp(fuel, start)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, totalFuel: int) -> int:
		n = len(locations)
		mod = int(1000000000.0 + 7)
		dp = [[-1] * (totalFuel + 1) for i in range(n)]

		def getNums(current, fuel):
			nonlocal dp, n, finish, start, mod
			if fuel == 0:
				if current == finish:
					return 1
				return 0
			if dp[current][fuel] > -1:
				return dp[current][fuel]
			ans = 0
			if current == finish:
				ans = 1
			for i in range(n):
				if i != current and abs(locations[current] - locations[i]) <= fuel:
					ans = (ans + getNums(i, fuel - abs(locations[current] - locations[i]))) % mod
			dp[current][fuel] = ans
			return dp[current][fuel]
		return getNums(start, totalFuel) % mod


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		memo = {}

		def helper(fuell, curr):
			if (fuell, curr) in memo:
				return memo[fuell, curr]
			if fuell < 0:
				return 0
			x = 0
			if curr == locations[finish]:
				x = 1
			y = x + sum([helper(fuell - abs(loc - curr), loc) for loc in locations if loc != curr]) % (10 ** 9 + 7)
			memo[fuell, curr] = y
			return y
		return helper(fuel, locations[start])


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		start_loc = locations[start]
		finish_loc = locations[finish]
		locations.sort()
		start = bisect_left(locations, start_loc)
		finish = bisect_left(locations, finish_loc)

		@lru_cache(None)
		def dp(cur, cur_fuel):
			return total
		dp = [[-1] * (fuel + 1) for _ in range(len(locations))]

		def f(cur, cur_fuel):
			if dp[cur][cur_fuel] != -1:
				return dp[cur][cur_fuel]
			if abs(locations[cur] - locations[finish]) > fuel:
				return 0
			total = 1 if cur == finish else 0
			for i in range(cur + 1, len(locations)):
				dist = locations[i] - locations[cur]
				if dist <= cur_fuel:
					total += f(i, cur_fuel - dist)
				else:
					break
			for i in reversed(list(range(0, cur))):
				dist = locations[cur] - locations[i]
				if dist <= cur_fuel:
					total += f(i, cur_fuel - dist)
				else:
					break
			dp[cur][cur_fuel] = total
			return total
		return f(start, fuel) % 1000000007


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		N = len(locations)

		@lru_cache(None)
		def dp(i, k):
			if k < 0:
				return 0
			ans = 1 if i == finish else 0
			for j in range(N):
				if i == j:
					continue
				ans += dp(j, k - abs(locations[i] - locations[j]))
			ans %= 1000000007
			return ans
		return dp(start, fuel)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		found = {}

		def count(cstart, cfuel):
			if (cstart, cfuel) in found:
				return found[cstart, cfuel]
			if cfuel < 0:
				return 0
			if cfuel == 0:
				return cstart == finish
			r = int(cstart == finish)
			for (i, l) in enumerate(locations):
				if i != cstart:
					r += count(i, cfuel - abs(locations[i] - locations[cstart]))
			found[cstart, cfuel] = r % (10 ** 9 + 7)
			return found[cstart, cfuel]
		return count(start, fuel)


class Solution:

	def countRoutes(self, locations, start, finish, fuel):
		n = len(locations)
		MOD = 10 ** 9 + 7

		@lru_cache(None)
		def dp(i, k):
			return (i == finish) + sum((dp(j, k - abs(locations[i] - locations[j])) for j in range(n) if i != j)) % MOD if k >= 0 else 0
		return dp(start, fuel)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:

		def dp(curr_loc, fuel):
			if (curr_loc, fuel) in memo:
				return memo[curr_loc, fuel]
			if fuel < 0:
				return 0
			ans = 0
			if curr_loc == finish:
				ans = 1
			for (i, loc) in enumerate(locations):
				if i != curr_loc:
					ans += dp(i, fuel - abs(locations[curr_loc] - loc))
			memo[curr_loc, fuel] = ans
			return ans
		memo = {}
		return dp(start, fuel) % (10 ** 9 + 7)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		mod = 10 ** 9 + 7
		return self.dfs(locations, start, finish, fuel, {}) % mod

	def dfs(self, locations, start, finish, fuel, memo):
		if (start, fuel) in memo:
			return memo[start, fuel]
		if fuel < 0:
			return 0
		count = 0
		if start == finish:
			count += 1
		for i in range(len(locations)):
			diff = abs(locations[i] - locations[start])
			if i == start:
				continue
			count += self.dfs(locations, i, finish, fuel - diff, memo)
		memo[start, fuel] = count % (10 ** 9 + 7)
		return memo[start, fuel]


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		MOD = 10 ** 9 + 7

		@lru_cache(None)
		def dp(cur, fuel):
			if fuel < 0:
				return 0
			ret = 1 if cur == finish else 0
			for i in range(len(locations)):
				if i == cur:
					continue
				ret += dp(i, fuel - abs(locations[i] - locations[cur]))
			return ret % MOD
		return dp(start, fuel)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		n = len(locations)
		mem = {}
		mod = 10 ** 9 + 7

		def helper(ind, f):
			cnt = 0
			if (ind, f) in mem:
				return mem[ind, f]
			if ind < 0 or ind > n - 1:
				return 0
			if ind == finish and f >= 0:
				cnt += 1
			for i in range(n):
				if i != ind and f - abs(locations[ind] - locations[i]) >= 0:
					cnt += helper(i, f - abs(locations[ind] - locations[i])) % mod
			mem[ind, f] = cnt
			return cnt % mod
		return helper(start, fuel) % mod


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		shortest = {finish: 0}
		ans = 0
		heap = sorted([[abs(locations[i] - locations[finish]), i] for i in range(len(locations))])
		while len(shortest) < len(locations):
			(d, i) = heapq.heappop(heap)
			if i in shortest:
				continue
			shortest[i] = d
			for j in range(len(locations)):
				if j not in shortest and j != finish:
					heapq.heappush(heap, [abs(locations[j] - locations[i]) + d, j])

		@lru_cache(None)
		def dfs(cur, fuel):
			if fuel < shortest[cur]:
				return 0
			if fuel == 0:
				if cur != finish:
					return 0
				else:
					return 1
			ans = 0
			if cur == finish:
				ans += 1
			for i in range(len(locations)):
				cost = abs(locations[i] - locations[cur])
				if i != cur and cost <= fuel:
					ans += dfs(i, fuel - cost) % 1000000007
			return ans % 1000000007
		return dfs(start, fuel)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		return self.helper(locations, start, finish, fuel, {})

	def helper(self, locations, start, finish, fuel, memo):
		if fuel < 0:
			return 0
		if (start, fuel) in memo:
			return memo[start, fuel]
		result = 0
		if start == finish:
			result = 1
		for i in range(len(locations)):
			if i != start:
				result = (result + self.helper(locations, i, finish, fuel - abs(locations[i] - locations[start]), memo)) % 1000000007
		memo[start, fuel] = result
		return result


from functools import lru_cache

class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		mod = 10 ** 9 + 7

		@lru_cache(None)
		def dfs(source, fuel):
			if fuel < 0:
				return 0
			cnt = 0
			if source == finish:
				cnt += 1
			for (i, val) in enumerate(locations):
				if i != source:
					cnt += dfs(i, fuel - abs(locations[source] - val))
			return cnt % mod
		return dfs(start, fuel)


from typing import List
from collections import deque

class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:

		def aux(curr, tel):
			if tel < 0:
				return 0
			if (curr, tel) in dp:
				return dp[curr, tel]
			ans = 1 if curr == finish else 0
			for i in range(len(locations)):
				if i != curr:
					ans += aux(i, tel - abs(locations[i] - locations[curr])) % M
			dp[curr, tel] = ans % M
			return ans % M
		M = 10 ** 9 + 7
		dp = dict()
		return aux(start, fuel) % M


from functools import lru_cache

class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		mod = 10 ** 9 + 7

		@lru_cache(None)
		def dfs(state, remain):
			if remain < 0:
				return 0
			cnt = 0
			if state == finish:
				cnt += 1
			for (next_state, next_loc) in enumerate(locations):
				if next_state == state:
					continue
				cnt += dfs(next_state, remain - abs(locations[state] - next_loc))
			return cnt % mod
		return dfs(start, fuel)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		MOD = 10 ** 9 + 7
		dp = [[-1] * (len(locations) + 1)] * fuel

		@lru_cache(None)
		def routes(cur_city, fuel):
			nonlocal locations, dp
			if fuel < 0:
				return 0
			total = 0
			if cur_city == finish:
				total += 1
			for (i, val) in enumerate(locations):
				if i != cur_city:
					total += routes(i, fuel - abs(locations[i] - locations[cur_city])) % MOD
			return total % MOD
		return routes(start, fuel)


class Solution:

	def countRoutes(self, locations, start: int, finish: int, fuel: int) -> int:

		@lru_cache(maxsize=None)
		def rec(start, finish, fuel):
			if fuel < 0:
				return 0
			if start == finish:
				res = 1
				for j in range(len(locations)):
					if j != start:
						res += rec(j, finish, fuel - abs(locations[start] - locations[j]))
				return res
			totalCounts = 0
			for j in range(len(locations)):
				if j != start:
					totalCounts += rec(j, finish, fuel - abs(locations[start] - locations[j]))
			return totalCounts
		return rec(start, finish, fuel) % (10 ** 9 + 7)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:

		def back_track(ci, fuel, N, mem):
			if (ci, fuel) in mem:
				return mem[ci, fuel]
			res = 0
			for i in range(N):
				if i != ci:
					if fuel - abs(locations[ci] - locations[i]) >= 0:
						res += (1 if i == finish else 0) + back_track(i, fuel - abs(locations[ci] - locations[i]), N, mem)
			mem[ci, fuel] = res
			return mem[ci, fuel]
		return (back_track(start, fuel, len(locations), defaultdict()) + (1 if start == finish else 0)) % (10 ** 9 + 7)


class Solution:

	def countRoutes(self, locations: [int], start: int, finish: int, fuel: int) -> int:
		d = {}
		start = locations[start]
		finish = locations[finish]
		for x in locations:
			d[x] = [0] * 201
		d[start][fuel] = 1
		ans = 0
		for fu in range(200, 0, -1):
			for loc in d:
				if d[loc][fu] != 0:
					for x in d:
						if x == loc:
							continue
						result = fu - abs(x - loc)
						if result >= 0:
							d[x][result] += d[loc][fu]
							d[x][result] %= 10 ** 9 + 7
		return sum(d[finish]) % (10 ** 9 + 7)
print(Solution().countRoutes([2, 3, 6, 8, 4], 1, 3, 5))


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		m = collections.defaultdict(lambda : 0)
		n = len(locations)
		for i in range(n):
			for j in range(n):
				if i == j:
					continue
				else:
					m[i, j] = abs(locations[i] - locations[j])
		memo = {}
		MOD = 10 ** 9 + 7

		def dfs(cur, target, fuel):
			nonlocal n
			if fuel < 0:
				return 0
			elif (cur, fuel) in memo:
				return memo[cur, fuel]
			else:
				cnt = 1 if cur == target else 0
				for i in range(n):
					if i != cur:
						cnt += dfs(i, target, fuel - m[i, cur])
				memo[cur, fuel] = cnt
				return memo[cur, fuel]
		return dfs(start, finish, fuel) % MOD


import numpy as np
MOD = 10 ** 9 + 7
cache = None
locations = None

def count(current, finish, fuel):
	if cache[current, fuel] >= 0:
		return cache[current, fuel]
	if abs(locations[current] - locations[finish]) > fuel:
		cache[current, fuel] = 0
		return 0
	routes = 1 if current == finish else 0
	for i in range(0, len(locations)):
		if i == current:
			continue
		distance = abs(locations[current] - locations[i])
		remaining = fuel - distance
		if remaining >= 0:
			routes += count(i, finish, remaining)
	cache[current, fuel] = routes % MOD
	return cache[current, fuel]

class Solution:

	def countRoutes(self, locs: List[int], start: int, finish: int, fuel: int) -> int:
		nonlocal cache, locations
		locations = locs
		cache = np.full((len(locations), fuel + 1), -1)
		return count(start, finish, fuel)


import heapq as hq

class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		start_loc = locations[start]
		finish_loc = locations[finish]
		locations = sorted(locations)
		start = locations.index(start_loc)
		finish = locations.index(finish_loc)
		pushed = set([(fuel, start, 1), (start, fuel, -1)])
		h = [(-fuel, start, 1), (-fuel, start, -1)]
		routes = {(start, fuel, 1): 1, (start, fuel, -1): 1}
		count = 0
		if start == finish:
			count = 1
		while len(h) > 0:
			(neg_fuel, st, di) = hq.heappop(h)
			ed = st + di
			inc = routes[st, -neg_fuel, di]
			while True:
				if ed < 0 or ed > len(locations) - 1:
					break
				new_fuel = -neg_fuel - abs(locations[ed] - locations[st])
				if new_fuel < 0:
					break
				if (new_fuel, ed, -di) not in pushed:
					pushed.add((new_fuel, ed, -di))
					routes[ed, new_fuel, -di] = inc
					hq.heappush(h, (-new_fuel, ed, -di))
				else:
					routes[ed, new_fuel, -di] += inc
				if ed == finish:
					count += inc
				ed += di
				inc *= 2
		return count % 1000000007


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		self.memo = {}
		return self.dfs(start, finish, fuel, locations) % (10 ** 9 + 7)

	def dfs(self, curr_loc, finish, curr_fuel, locations):
		if (curr_loc, curr_fuel) in self.memo:
			return self.memo[curr_loc, curr_fuel]
		if curr_fuel < 0:
			return 0
		ways = 0 if curr_loc != finish else 1
		for i in range(len(locations)):
			if i == curr_loc:
				continue
			ways += self.dfs(i, finish, curr_fuel - abs(locations[i] - locations[curr_loc]), locations)
		self.memo[curr_loc, curr_fuel] = ways
		return ways


class Solution:

	def countRoutes(self, A: list, start: int, finish: int, fuel: int) -> int:
		n = len(A)
		MOD = 10 ** 9 + 7

		@functools.lru_cache(None)
		def dp(i, k):
			if k < 0:
				return 0
			ans = 1 if i == finish else 0
			for j in range(n):
				if i == j:
					continue
				ans += dp(j, k - abs(A[i] - A[j]))
			return ans % MOD
		return dp(start, fuel)


from functools import lru_cache

class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		MOD = 10 ** 9 + 7

		@lru_cache(None)
		def td_solve(gas, s):
			if gas < abs(locations[s] - locations[finish]):
				return 0
			res = 1 if s == finish else 0
			for city in range(len(locations)):
				if city == s:
					continue
				res += td_solve(gas - abs(locations[city] - locations[s]), city)
				res %= MOD
			return res
		return td_solve(fuel, start)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		n = len(locations)

		@lru_cache(None)
		def dfs(l, f):
			res = 1 if l == finish else 0
			for i in range(n):
				diff = abs(locations[i] - locations[l])
				if i != l and diff <= f:
					res += dfs(i, f - diff)
			return res
		return dfs(start, fuel) % (10 ** 9 + 7)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		self.memo = {}
		self.mod = 10 ** 9 + 7
		return self.helper(start, finish, locations, fuel)

	def helper(self, curr, finish, locations, fuel):
		if fuel < 0:
			return 0
		if (curr, fuel) in self.memo:
			return self.memo[curr, fuel]
		res = 1 if curr == finish else 0
		for next_i in range(len(locations)):
			if next_i != curr:
				update = abs(locations[next_i] - locations[curr])
				res += self.helper(next_i, finish, locations, fuel - update)
		res = res % self.mod
		self.memo[curr, fuel] = res
		return res


MOD = 10 ** 9 + 7

class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		self.finish = finish
		self.locations = locations
		mem = {}
		res = self.dp(start, fuel, mem)
		return res % MOD

	def dp(self, st, fuel, mem):
		if (st, fuel) in mem:
			return mem[st, fuel]
		res = 1 if st == self.finish else 0
		for mid in range(len(self.locations)):
			if mid == st:
				continue
			if abs(self.locations[mid] - self.locations[st]) > fuel:
				continue
			res += self.dp(mid, fuel - abs(self.locations[mid] - self.locations[st]), mem)
		mem[st, fuel] = res
		return res


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		mod = 1000000007
		n = len(locations)

		@functools.lru_cache(None)
		def dfs(cur, target, tot):
			res = 0
			for i in range(n):
				if i == cur:
					if i == finish:
						res += 1
					continue
				if tot + abs(locations[cur] - locations[i]) > fuel:
					continue
				else:
					res += dfs(i, target, tot + abs(locations[cur] - locations[i]))
					res %= mod
			return res
		return dfs(start, finish, 0)


class Solution:

	def _help(self, locations, start, finish, fuel, dp):
		if fuel < 0:
			return 0
		elif dp[fuel][start] is not None:
			return dp[fuel][start]
		ni = 1 if start == finish else 0
		for (i, loc) in enumerate(locations):
			if i != start:
				ni += self._help(locations, i, finish, fuel - abs(locations[i] - locations[start]), dp)
		dp[fuel][start] = ni
		return ni

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		n = len(locations)
		dp = [[None] * n for _ in range(fuel + 1)]
		self._help(locations, start, finish, fuel, dp)
		return dp[-1][start] % 1000000007


from functools import lru_cache

class Solution:
	locations = list()

	@lru_cache(None)
	def helper(self, start, finish, fuel):
		if fuel < abs(self.locations[start] - self.locations[finish]):
			return 0
		res = 0
		for (i, v) in enumerate(self.locations):
			if i != start:
				res += self.helper(i, finish, fuel - abs(v - self.locations[start]))
		if start == finish:
			res += 1
		return res

	def countRoutes(self, l, start, finish, fuel):
		self.locations = l
		return self.helper(start, finish, fuel) % 1000000007


class Solution:

	def solve(self, curr_loc, fuel):
		if fuel < 0:
			return 0
		if (curr_loc, fuel) in self.dp:
			return self.dp[curr_loc, fuel]
		ways = 0
		if curr_loc == self.finish:
			ways += 1
		for i in range(len(self.locations)):
			if i != curr_loc:
				ways += self.solve(i, fuel - abs(self.locations[i] - self.locations[curr_loc]))
		self.dp[curr_loc, fuel] = ways % self.modz
		return ways

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		self.locations = locations
		self.dp = {}
		self.modz = pow(10, 9) + 7
		self.finish = finish
		return self.solve(start, fuel) % self.modz


class Solution:

	def countRoutes(self, a: List[int], s: int, e: int, fuel: int) -> int:
		n = len(a)
		mod = 10 ** 9 + 7
		memo = {}

		def dp(u, f):
			if f < 0:
				return 0
			if (u, f) in memo:
				return memo[u, f]
			ans = 0
			if u == e:
				ans += 1
			for v in range(n):
				if v != u:
					ans += dp(v, f - abs(a[u] - a[v]))
					ans %= mod
			memo[u, f] = ans
			return ans
		return dp(s, fuel)


class Solution:

	def countRoutes(self, l: List[int], start: int, fin: int, fuel: int) -> int:
		(a, b, i) = (l[start], l[fin], 0)
		while i < len(l):
			if abs(l[i] - a) + abs(l[i] - b) > fuel:
				del l[i]
			else:
				i += 1
		if not l:
			return 0
		n = len(l)
		(start, fin) = (l.index(a), l.index(b))

		@lru_cache(None)
		def dfs(i: int, f: int) -> int:
			return 0 if f < 0 else (1 if i == fin else 0) + sum((0 if i == j else dfs(j, f - abs(l[j] - l[i])) for j in range(len(l))))
		return dfs(start, fuel) % 1000000007


class Solution:

	def countRoutes(self, locations, start: int, finish: int, fuel: int) -> int:
		KMAX = 10 ** 9 + 7
		N = len(locations)
		mem = dict()

		def dp(city, gas):
			if (city, gas) in mem:
				return mem[city, gas]
			if gas < 0:
				return 0
			mem[city, gas] = 1 if city == finish else 0
			for i in range(N):
				if i == city or abs(locations[i] - locations[city]) > gas:
					continue
				mem[city, gas] += dp(i, gas - abs(locations[i] - locations[city]))
			return mem[city, gas]
		res = dp(start, fuel) % KMAX
		return res


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:

		@functools.lru_cache(None)
		def get(start=start, fuel=fuel):
			if fuel < abs(locations[start] - locations[finish]):
				return 0
			to_ret = 1 if start == finish else 0
			for p in range(len(locations)):
				if p == start:
					continue
				to_ret += get(p, fuel=max(0, fuel - abs(locations[start] - locations[p])))
			return to_ret % (10 ** 9 + 7)
		return get()


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		mod = 10 ** 9 + 7

		@functools.lru_cache(None)
		def drive(i, fuel):
			res = 0
			if i == finish:
				res += 1
			for j in range(len(locations)):
				if i == j:
					continue
				dist = abs(locations[i] - locations[j])
				if dist <= fuel:
					res += drive(j, fuel - dist) % mod
			return res % mod
		return drive(start, fuel)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		dp = {}
		n = len(locations)
		mod = 10 ** 9 + 7

		def rec(start, end, fuel, n):
			res = 0
			if fuel < 0:
				return res
			if (start, end, fuel) in dp:
				return dp[start, end, fuel]
			if start == end:
				res += 1
			for i in range(n):
				if i == start:
					continue
				res += rec(i, end, fuel - abs(locations[i] - locations[start]), n)
			dp[start, end, fuel] = res
			return res
		return rec(start, finish, fuel, n) % mod


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		memo = {}

		def dp(ind, rem_fuel):
			if (ind, rem_fuel) in memo:
				return memo[ind, rem_fuel]
			num_ways = 0
			for city in range(len(locations)):
				used = abs(locations[ind] - locations[city])
				if used <= rem_fuel and city != ind:
					num_ways += dp(city, rem_fuel - used)
					if city == finish:
						num_ways += 1
			memo[ind, rem_fuel] = num_ways
			return memo[ind, rem_fuel]
		res = dp(start, fuel)
		if start == finish:
			res += 1
		return res % (10 ** 9 + 7)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		n = len(locations)
		MOD = 10 ** 9 + 7

		@lru_cache(None)
		def dp(f, fuel):
			if fuel < 0:
				return 0
			ans = 0
			if f == finish:
				ans = 1
			for t in range(0, n):
				if t != f:
					ans += dp(t, fuel - abs(locations[f] - locations[t]))
					ans %= MOD
			return ans
		return dp(start, fuel)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		(locationsLen, modulus) = (len(locations), 10 ** 9 + 7)
		dp = [[-1] * (fuel + 1) for _ in range(locationsLen)]

		def dfs(city, fuel):
			if fuel < 0:
				return 0
			if dp[city][fuel] != -1:
				return dp[city][fuel]
			result = 0
			if city == finish:
				result = 1
			for i in range(locationsLen):
				if i != city and fuel - abs(locations[i] - locations[city]) >= 0:
					result += dfs(i, fuel - abs(locations[i] - locations[city])) % modulus
			dp[city][fuel] = result
			return result
		return dfs(start, fuel) % modulus


from functools import lru_cache

class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		mod = 10 ** 9 + 7

		@lru_cache(maxsize=None)
		def dfs(i, fuel):
			total = 1 if i == finish else 0
			if fuel < 0:
				return 0
			for j in range(len(locations)):
				if j != i:
					leftFuel = fuel - abs(locations[i] - locations[j])
					total += dfs(j, leftFuel)
					total = total % mod
			return total
		return dfs(start, fuel)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		MOD = 10 ** 9 + 7

		def dp(i, f, memo):
			if i == finish and f == 0:
				return 1
			if (i, f) not in memo:
				ans = int(i == finish)
				for j in range(len(locations)):
					d = abs(locations[j] - locations[i])
					if i != j and f >= d:
						ans += dp(j, f - d, memo)
						ans %= MOD
				memo[i, f] = ans
			return memo[i, f]
		return dp(start, fuel, {})


import sys
sys.setrecursionlimit(1000)

class Solution:

	def rec(self, p, f):
		if f < 0:
			return 0
		if self.memo[p][f] != -1:
			return self.memo[p][f]
		res = 1 if p == self.start else 0
		for i in range(len(self.locations)):
			if i == p:
				continue
			res += self.rec(i, f - abs(self.locations[p] - self.locations[i]))
			res %= self.MOD
		self.memo[p][f] = res
		return res

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		self.locations = locations
		self.start = start
		self.memo = [[-1] * (fuel + 1) for _ in range(len(locations))]
		self.MOD = 10 ** 9 + 7
		return self.rec(finish, fuel)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		mod = 10 ** 9 + 7

		@lru_cache(None)
		def count(n):
			if n == 0:
				return 1
			ans = 0
			for i in range(1, n + 1):
				ans += count(n - i)
			return ans
		dct = defaultdict(int)
		for (i, l) in enumerate(locations):
			dct[l] = i
		(start_location, end_location) = (locations[start], locations[finish])
		(start_idx, end_idx) = (dct[start_location], dct[end_location])

		@lru_cache(None)
		def dfs(idx, fuel):
			ans = 0
			if idx == end_idx:
				ans += 1
			for (i, l) in enumerate(locations):
				if i != idx and abs(l - locations[idx]) <= fuel:
					ans += dfs(i, fuel - abs(l - locations[idx]))
			return ans % mod
		return dfs(start_idx, fuel)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		mem = {}

		def get_val(point, fuel):
			nonlocal finish
			value = mem.get((point, fuel), None)
			if value != None:
				return value
			mem[point, fuel] = 0
			if point == finish:
				mem[point, fuel] = 1
			for i in range(len(locations)):
				if i != point:
					if fuel - abs(locations[i] - locations[point]) >= 0:
						mem[point, fuel] += get_val(i, fuel - abs(locations[i] - locations[point]))
			return mem[point, fuel]
		v = get_val(start, fuel)
		return v % (10 ** 9 + 7)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		n = len(locations)
		memo = [[-1] * (fuel + 1) for i in range(n)]
		mod = 10 ** 9 + 7

		def dp(curr, fuel):
			if fuel < 0:
				return 0
			if memo[curr][fuel] != -1:
				return memo[curr][fuel]
			memo[curr][fuel] = 1 if curr == finish else 0
			for (i, city) in enumerate(locations):
				if i != curr:
					memo[curr][fuel] += dp(i, fuel - abs(city - locations[curr]))
					memo[curr][fuel] %= mod
			return memo[curr][fuel]
		return dp(start, fuel)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		a = locations
		n = len(a)
		MOD = 10 ** 9 + 7

		@lru_cache(maxsize=None)
		def dp(pos, fuel):
			res = 0
			if pos == finish:
				res = 1
			for k in range(n):
				dist = abs(a[pos] - a[k])
				if dist > 0 and dist <= fuel:
					res = (res + dp(k, fuel - dist)) % MOD
			return res
		return dp(start, fuel)


MOD = 10 ** 9 + 7

def gen_matrix(m, n, elem):
	return [[elem for col in range(n)] for row in range(m)]

def count_routes(cities, start, finish, fuel):
	m_routes = gen_matrix(fuel + 1, len(cities), None)

	def dist(c1, c2):
		return abs(cities[c1] - cities[c2])

	def routes(f, c):
		if f < 0:
			return 0
		if m_routes[f][c] is not None:
			return m_routes[f][c]
		if f == 0 and c != finish:
			ans = 0
		else:
			current_sol = bool(c == finish)
			ans = current_sol + sum((routes(f - dist(c, c2), c2) for c2 in range(len(cities)) if c2 != c))
			ans %= MOD
		m_routes[f][c] = ans
		return ans
	return routes(fuel, start)

class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		return count_routes(locations, start, finish, fuel)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		dp = {}
		M = 10 ** 9 + 7

		def go(now, f):
			if (now, f) in dp:
				return dp[now, f]
			if f < 0:
				return 0
			dp[now, f] = 1 if now == finish else 0
			for (i, v) in enumerate(locations):
				if i != now and f - abs(locations[now] - v) >= 0:
					dp[now, f] += go(i, f - abs(locations[now] - v))
			dp[now, f] %= M
			return dp[now, f]
		return go(start, fuel)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:

		@lru_cache(None)
		def routes(start, fuel):
			if fuel < 0:
				return 0
			answer = 0
			if start == finish:
				answer += 1
			for i in range(len(locations)):
				if i == start:
					continue
				answer += routes(i, fuel - abs(locations[i] - locations[start]))
			return answer
		return routes(start, fuel) % 1000000007


from functools import lru_cache

class Solution:

	@lru_cache(None)
	def recursive(self, i, f):
		ans = 0
		if i == self.t:
			ans += 1
		if f > 0:
			j = i + 1
			while j < self.n and self.L[j] - self.L[i] + self.m[j] <= f:
				ans += self.recursive(j, f - (self.L[j] - self.L[i]))
				j += 1
			j = i - 1
			while j > -1 and self.L[i] - self.L[j] + self.m[j] <= f:
				ans += self.recursive(j, f - (self.L[i] - self.L[j]))
				j -= 1
		return ans

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		self.n = len(locations)
		(sx, tx) = (locations[start], locations[finish])
		self.L = sorted(locations)
		self.d = {x: i for (i, x) in enumerate(self.L)}
		(self.s, self.t) = (self.d[sx], self.d[tx])
		self.m = {i: abs(x - tx) for (i, x) in enumerate(self.L)}
		self.recursive.cache_clear()
		return self.recursive(self.s, fuel) % (10 ** 9 + 7)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		n = len(locations)
		self.ans = 0

		@lru_cache(None)
		def back(curr, fuel):
			aux = 0
			if curr == finish:
				aux += 1
			for i in range(n):
				if i != curr:
					if fuel - abs(locations[curr] - locations[i]) >= 0:
						aux += back(i, fuel - abs(locations[curr] - locations[i]))
			return aux
		return back(start, fuel) % (10 ** 9 + 7)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		n = len(locations)
		dist = [[abs(locations[i] - locations[j]) for j in range(n)] for i in range(n)]
		min_d = [min((dist[i][j] for j in range(n) if j != i)) for i in range(n)]
		memo = {}

		def dp(begin, left):
			if left < min_d[begin]:
				return 1 if begin == finish else 0
			if (begin, left) in memo:
				return memo[begin, left]
			memo[begin, left] = sum((dp(i, left - dist[begin][i]) for i in range(n) if i != begin and left >= dist[begin][i]))
			if begin == finish:
				memo[begin, left] += 1
			return memo[begin, left]
		return dp(start, fuel) % (10 ** 9 + 7)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:

		def recurse(index, fuel, finish):
			paths = 0
			if fuel < 0:
				return 0
			if index == finish:
				paths += 1
			if dp[index][fuel] != -1:
				return dp[index][fuel]
			for i in range(len(locations)):
				if i == index:
					continue
				paths += recurse(i, fuel - abs(locations[i] - locations[index]), finish)
			dp[index][fuel] = paths % (pow(10, 9) + 7)
			return paths
		dp = [[-1 for i in range(fuel + 1)] for j in range(len(locations))]
		totalpaths = recurse(start, fuel, finish) % (pow(10, 9) + 7)
		return totalpaths


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:

		@lru_cache(None)
		def dp(i, f):
			if i == finish:
				res = 1
			else:
				res = 0
			for j in range(len(locations)):
				if j != i and abs(locations[i] - locations[j]) <= f:
					res += dp(j, f - abs(locations[i] - locations[j]))
			return res
		return dp(start, fuel) % (10 ** 9 + 7)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		dp = {}

		def dfs(s, f, fuel):
			if fuel < 0:
				return 0
			ans = 0
			if (s, f, fuel) in dp:
				return dp[s, f, fuel]
			if s == finish:
				ans += 1
			for i in range(len(locations)):
				if i != s:
					ans += dfs(i, f, fuel - abs(locations[i] - locations[s]))
			ans = ans % (10 ** 9 + 7)
			dp[s, f, fuel] = ans
			return ans
		return dfs(start, finish, fuel)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		q = [(start, fuel)]
		res = 0
		if start == finish:
			res += 1
		next_q = []

		@lru_cache(None)
		def dp(cur_start, fuel):
			res = 0
			for l in range(len(locations)):
				left_fuel = fuel - abs(locations[l] - locations[cur_start])
				if l != cur_start and left_fuel >= 0:
					if l == finish:
						res += 1
					if left_fuel > 0:
						res += dp(l, left_fuel)
			return res
		res += dp(start, fuel)
		return res % (10 ** 9 + 7)


class Solution:

	def countRoutes(self, loct: List[int], start: int, finish: int, fuel: int) -> int:
		n = len(loct)

		def getf(s, e):
			return abs(loct[s] - loct[e])
		visited = set()

		@functools.lru_cache(None)
		def dfs(start, f):
			if f < 0:
				return 0
			return sum([dfs(i, f - getf(start, i)) for i in range(n) if i != start]) + (1 if start == finish else 0)
		return dfs(start, fuel) % (10 ** 9 + 7)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		mod = 10 ** 9 + 7

		def dp(cur, fuel):
			if fuel < 0:
				return 0
			if (cur, fuel) in memo:
				return memo[cur, fuel]
			ans = 0
			if cur == locations[finish]:
				ans = 1
			for loc in locations:
				if loc != cur:
					ans += dp(loc, fuel - abs(cur - loc))
			memo[cur, fuel] = ans
			return ans
		memo = {}
		return dp(locations[start], fuel) % mod


class Solution:

	def search(self, locations: List[int], left: int, right: int, target: int):
		while left <= right:
			mid = (left + right) // 2
			if locations[mid] < target:
				left = mid + 1
			elif left == right:
				break
			else:
				right = mid
		return left

	def dfs(self, locations: List[int], start: int, finish: int, fuel: int, memo: List[Dict[int, int]]):
		if fuel in memo[start]:
			return memo[start][fuel]
		if fuel < abs(locations[start] - locations[finish]):
			return 0
		res = 1 if start == finish else 0
		left = self.search(locations, 0, start, locations[start] - fuel)
		right = self.search(locations, start, len(locations) - 1, locations[start] + fuel + 1)
		for next in range(left, right):
			if next == start:
				continue
			res += self.dfs(locations, next, finish, fuel - abs(locations[start] - locations[next]), memo)
		memo[start][fuel] = res % 1000000007
		return memo[start][fuel]

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		startLoc = locations[start]
		finishLoc = locations[finish]
		locations.sort()
		start = self.search(locations, 0, len(locations) - 1, startLoc)
		finish = self.search(locations, 0, len(locations) - 1, finishLoc)
		print((locations, start, finish))
		return self.dfs(locations, start, finish, fuel, [{} for i in range(len(locations))])


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		startFuel = fuel
		memo = [[-1 for f in range(fuel + 1)] for l in range(len(locations))]

		def recurse(start, fuel, memo):
			numRoutes = 0
			if fuel >= 0:
				if memo[start][fuel] != -1:
					numRoutes = memo[start][fuel]
				else:
					if start == finish:
						numRoutes += 1
					for nextCity in range(0, len(locations)):
						if nextCity != start:
							numRoutes += recurse(nextCity, fuel - abs(locations[nextCity] - locations[start]), memo)
					memo[start][fuel] = numRoutes
			return numRoutes
		return recurse(start, fuel, memo) % (10 ** 9 + 7)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		cache = {}

		def dfs(start, fuel):
			if (start, fuel) not in cache:
				res = 0
				for c in range(len(locations)):
					if c == start:
						continue
					dist = abs(locations[start] - locations[c])
					if c == finish and dist <= fuel:
						res += 1
					if dist <= fuel:
						res += dfs(c, fuel - dist)
				cache[start, fuel] = res % (10 ** 9 + 7)
			return cache[start, fuel]
		return dfs(start, fuel) + int(start == finish)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		MOD = 10 ** 9 + 7

		@functools.lru_cache(None)
		def run(c, f):
			res = 0
			if c == finish:
				res += 1
			if f > 0:
				for i in range(len(locations)):
					if i != c and abs(locations[c] - locations[i]) <= f:
						res += run(i, f - abs(locations[c] - locations[i])) % MOD
			return res % MOD
		return run(start, fuel)


from functools import lru_cache

class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		MOD = 10 ** 9 + 7

		@lru_cache(None)
		def ways(left, city):
			if left > fuel:
				return 0
			if city == locations[start] and left == fuel:
				return 1
			return sum((ways(abs(city - city_) + left, city_) for city_ in locations if city != city_)) % MOD
		return sum((ways(left, locations[finish]) for left in range(fuel + 1))) % MOD


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		dp = {}
		self.mode = int(1000000000.0) + 7
		return self.dfs(fuel, start, finish, locations, dp)

	def dfs(self, fuel, u, target, locations, dp):
		if fuel < 0:
			return 0
		if (fuel, u, target) in dp:
			return dp[fuel, u, target]
		ans = 1 if u == target else 0
		for v in range(len(locations)):
			if u == v:
				continue
			ans += self.dfs(fuel - abs(locations[u] - locations[v]), v, target, locations, dp)
			ans %= self.mode
		dp[fuel, u, target] = ans
		return ans


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:

		@functools.lru_cache(maxsize=None)
		def helper(L, i, j, fuel):
			output = 0
			if fuel < 0:
				return output
			if i == j and fuel >= 0:
				output = 1
			if fuel > 0:
				for k in range(len(locations)):
					if i == k:
						continue
					output += helper(L, k, j, fuel - abs(locations[i] - locations[k]))
			return output
		return helper(tuple(locations), start, finish, fuel) % (10 ** 9 + 7)


class Solution:
	MODULO = 10 ** 9 + 7

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		my_dp = dict()
		return Solution.get_dp(my_dp, locations, start, finish, fuel)

	@staticmethod
	def get_dp(dp, locations, start, finish, fuel):
		if (start, finish, fuel) not in dp:
			total_ways = 0
			if start == finish:
				total_ways = 1
			for (idx, pos) in enumerate(locations):
				if idx != start and abs(locations[start] - locations[idx]) <= fuel:
					total_ways = (total_ways + Solution.get_dp(dp, locations, idx, finish, fuel - abs(locations[start] - locations[idx]))) % Solution.MODULO
			dp[start, finish, fuel] = total_ways
		return dp[start, finish, fuel]


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		self.locations = locations
		self.nr = [[0] * (fuel + 1) for _ in locations]
		self.evaluated = [[False] * (fuel + 1) for _ in locations]
		for i in range(len(locations) - 1):
			self.nr[i][0] = 0
			self.evaluated[i][0] = True
		for i in range(fuel + 1):
			self.nr[finish][i] = 1
		self.evaluated[finish][0] = True
		x = self.num_routes(start, finish, fuel)
		return x

	def num_routes(self, current_city, end, current_fuel):
		if self.evaluated[current_city][current_fuel]:
			return self.nr[current_city][current_fuel]
		cur_nr = self.nr[current_city][current_fuel]
		for target_city in range(len(self.locations)):
			if target_city == current_city:
				continue
			remaining_fuel = current_fuel - max(self.locations[current_city] - self.locations[target_city], self.locations[target_city] - self.locations[current_city])
			if remaining_fuel >= 0:
				cur_nr += self.num_routes(target_city, end, remaining_fuel)
		cur_nr = cur_nr % (10 ** 9 + 7)
		self.nr[current_city][current_fuel] = cur_nr
		self.evaluated[current_city][current_fuel] = True
		return cur_nr


MOD = 10 ** 9 + 7

class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		m = len(locations)
		n = fuel + 1
		mem = [[None for i in range(n)] for j in range(m)]
		return self.backtrack(start, locations, finish, fuel, mem)

	def backtrack(self, cur, locations, finish, fuel, mem):
		if fuel < 0:
			return 0
		elif mem[cur][fuel] != None:
			return mem[cur][fuel]
		count = 0
		if cur == finish:
			count += 1
		for (i, pos) in enumerate(locations):
			dist = abs(pos - locations[cur])
			if i == cur or dist > fuel:
				continue
			count += self.backtrack(i, locations, finish, fuel - dist, mem)
		mem[cur][fuel] = count % MOD
		return mem[cur][fuel]


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		self.memo = {}
		return self.dfs(start, fuel, finish, locations) % (10 ** 9 + 7)

	def dfs(self, cur, fuel, target, location):
		if cur == target:
			result = 1
		else:
			result = 0
		if (cur, fuel) in self.memo:
			return self.memo[cur, fuel]
		for i in range(len(location)):
			if cur != i and abs(location[i] - location[cur]) <= fuel:
				result += self.dfs(i, fuel - abs(location[i] - location[cur]), target, location)
		self.memo[cur, fuel] = result
		return result


MOD = 10 ** 9 + 7

class Solution:

	def countRoutes(self, locations, start, finish, fuel):
		dp = [[0 for _ in locations] for _ in range(fuel + 1)]
		dp[0][start] = 1
		for f in range(fuel + 1):
			for (i, x) in enumerate(locations):
				if abs(x - locations[finish]) > fuel - f:
					continue
				for (j, y) in enumerate(locations):
					if i == j:
						continue
					new = f + abs(x - y)
					if new > fuel:
						continue
					dp[new][j] = dp[new][j] + dp[f][i]
		return sum((row[finish] for row in dp)) % MOD


MAX = int(10 ** 9 + 7)

class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		A = [[None for _ in range(fuel + 1)] for _ in range(len(locations))]
		A[start][fuel] = 1
		for f in range(fuel, 0, -1):
			for ca in range(len(locations) - 1, -1, -1):
				if A[ca][f] is None:
					continue
				for cb in range(len(locations) - 1, -1, -1):
					if cb == ca:
						continue
					loss = int(abs(locations[ca] - locations[cb]))
					if loss > f:
						continue
					A[cb][f - loss] = ((A[cb][f - loss] or 0) + A[ca][f]) % MAX
		r = 0
		for x in A[finish]:
			if x is None:
				continue
			r = (r + x) % MAX
		return r


class Solution:

	def countRoutes(self, locations, start: int, finish: int, fuel: int) -> int:
		MOD = 10 ** 9 + 7
		dp = [[-1] * (len(locations) + 1) for _ in range(fuel + 1)]

		def recur(st, ed, f):
			if f < 0:
				return 0
			if dp[f][st] != -1:
				return dp[f][st]
			total = 0
			for i in range(len(locations)):
				if i != st:
					total += recur(i, ed, f - abs(locations[st] - locations[i]))
			if st == ed:
				answer = (total + 1) % MOD
			else:
				answer = total % MOD
			dp[f][st] = answer
			return answer
		recur(start, finish, fuel)
		return dp[fuel][start]


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		M = 10 ** 9 + 7

		@lru_cache(None)
		def dp(curLocation, curFuel):
			if curFuel > fuel:
				return 0
			nonlocal M
			count = 0
			for preLocation in locations:
				if preLocation == curLocation:
					continue
				preFuel = curFuel + abs(preLocation - curLocation)
				if preFuel > fuel or (preFuel == fuel and preLocation != locations[start]):
					continue
				if preLocation == locations[start] and preFuel == fuel:
					count = (count + 1) % M
				else:
					count = (count + dp(preLocation, preFuel)) % M
			return count % M
		ans = sum([dp(locations[finish], f) % M for f in range(fuel)]) % M
		return ans + 1 if start == finish else ans


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		if fuel < abs(locations[start] - locations[finish]):
			return 0
		mask = int(1000000000.0 + 7)
		table = [[0] * len(locations) for i in range(fuel + 1)]
		table[fuel][start] = 1
		for f in reversed(list(range(1, fuel + 1))):
			for loc1 in range(len(locations)):
				if table[f][loc1] == 0:
					continue
				for loc2 in range(len(locations)):
					if loc2 == loc1:
						continue
					fuel_required = abs(locations[loc1] - locations[loc2])
					if fuel_required <= f:
						table[f - fuel_required][loc2] += table[f][loc1]
		return sum([table[f][finish] for f in range(fuel + 1)]) % mask


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		start = locations[start]
		finish = locations[finish]
		locations.sort()
		res = 0
		dict = {}

		def dfs(start, finish, fuel):
			if (start, fuel) in dict:
				return dict[start, fuel]
			route = 0
			for val in locations:
				if val != start and abs(val - start) <= fuel:
					if val == finish:
						route += 1
					dict[val, fuel - abs(val - start)] = dfs(val, finish, fuel - abs(val - start))
					route += dict[val, fuel - abs(val - start)]
			return route
		res = dfs(start, finish, fuel)
		if start == finish:
			res += 1
		return res % (10 ** 9 + 7)


import collections

class Solution:

	def countRoutes(self, locations, start: int, finish: int, fuel: int) -> int:
		self.memorization = collections.defaultdict(int)

		def dfs_memorization(index, currentCityValue, destinationIndex, remainingFuel, locations):
			temp_count = 0
			if (index, currentCityValue, remainingFuel) in self.memorization:
				return self.memorization[index, currentCityValue, remainingFuel]
			if remainingFuel < 0:
				self.memorization[index, currentCityValue, remainingFuel] = 0
				return 0
			if remainingFuel == 0 and index == destinationIndex:
				self.memorization[index, currentCityValue, remainingFuel] = 1
				return 1
			if remainingFuel == 0 and index != destinationIndex:
				self.memorization[index, currentCityValue, remainingFuel] = 0
				return 0
			if index == destinationIndex:
				temp_count += 1
			for i in range(len(locations)):
				if i == index:
					continue
				temp_count += dfs_memorization(i, locations[i], destinationIndex, remainingFuel - abs(currentCityValue - locations[i]), locations)
			self.memorization[index, currentCityValue, remainingFuel] = temp_count
			return temp_count
		count = dfs_memorization(start, locations[start], finish, fuel, locations)
		return count % (10 ** 9 + 7)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		mod = 10 ** 9 + 7
		memo = {}

		def dp(pos, leftFuel):
			if memo.get((pos, leftFuel), None) is not None:
				return memo[pos, leftFuel]
			ans = 0
			if pos == finish:
				ans = 1
			for otherPos in range(len(locations)):
				if pos != otherPos and abs(locations[pos] - locations[otherPos]) <= leftFuel:
					ans += dp(otherPos, leftFuel - abs(locations[pos] - locations[otherPos]))
			memo[pos, leftFuel] = ans
			return ans
		ans = dp(start, fuel) % mod
		return ans


from functools import lru_cache

class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:

		@lru_cache(None)
		def dp(f, i):
			if (f, i) == (fuel, start):
				return 1
			ans = 0
			for j in range(n):
				if i == j:
					continue
				nd = f + abs(locations[j] - locations[i])
				if nd <= fuel:
					ans = (ans + dp(nd, j)) % md
			return ans
		(n, md) = (len(locations), 10 ** 9 + 7)
		res = 0
		for i in range(fuel + 1):
			res = (res + dp(i, finish)) % md
		return res


class Solution:
	d = {}

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		self.loc = sorted(locations)
		self.numloc = len(locations)
		self.num = 10 ** 9 + 7
		Solution.d = {}
		newstart = self.loc.index(locations[start])
		newfinish = self.loc.index(locations[finish])
		ways = self.cr(newstart, newfinish, fuel)
		if newstart == newfinish and ways == 0:
			return 1
		if newstart == newfinish:
			ways += 1
		return ways

	def cr(self, start, finish, fuel):
		if fuel < 0 or fuel < abs(self.loc[finish] - self.loc[start]):
			return 0
		if (start, fuel) in Solution.d:
			return Solution.d[start, fuel]
		minfuel = abs(self.loc[finish] - self.loc[start])
		if fuel <= minfuel + 1:
			Solution.d[start, fuel] = 2 ** (abs(finish - start) - 1)
			return Solution.d[start, fuel]
		ways = 0
		for i in range(self.numloc):
			if i != start:
				fuel1 = abs(self.loc[i] - self.loc[start])
				fuel2 = abs(self.loc[i] - self.loc[finish])
				if fuel1 + fuel2 <= fuel:
					ways += self.cr(i, finish, fuel - fuel1)
		if start != finish:
			ways += 1
		ways %= self.num
		Solution.d[start, fuel] = ways
		return ways


class Solution:

	def __init__(self, *args, **kwargs):
		self.mp = {}

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		if fuel < 0:
			return 0
		key = '{}-{}'.format(start, fuel)
		if key in self.mp:
			return self.mp[key]
		res = 1 if start == finish else 0
		for i in range(len(locations)):
			if i != start:
				res += self.countRoutes(locations, i, finish, fuel - abs(locations[start] - locations[i]))
		res %= 10 ** 9 + 7
		self.mp[key] = res
		return res


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		self.memo = {}
		self.mod = 10 ** 9 + 7
		ret = self.dp(locations, start, finish, fuel)
		return ret % self.mod

	def dp(self, locations, start, finish, fuel):
		if (start, fuel) in self.memo:
			return self.memo[start, fuel]
		if fuel < 0:
			return 0
		ans = 0
		if start == finish:
			ans += 1
		for (i, sf) in enumerate(locations):
			if i == start:
				continue
			ans += self.dp(locations, i, finish, fuel - abs(locations[i] - locations[start])) % self.mod
		self.memo[start, fuel] = ans
		return ans


class Solution:

	def countRoutesUtil(self, locations, currentLocation, target, fuelLeft, dp):
		if fuelLeft < 0:
			return 0
		key = (currentLocation, fuelLeft)
		if key in dp:
			return dp[key]
		result = 0
		if currentLocation == target:
			result += 1
		for i in range(len(locations)):
			if i != currentLocation:
				result += self.countRoutesUtil(locations, i, target, fuelLeft - abs(locations[i] - locations[currentLocation]), dp)
				result %= 10 ** 9 + 7
		dp[key] = result % (10 ** 9 + 7)
		return dp[key]

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		return self.countRoutesUtil(locations, start, finish, fuel, {})


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		mem = {}

		def count(start, end, fuel, mem):
			if fuel == 0 and start != end:
				return 0
			if not mem.get((start, fuel)) is None:
				return mem[start, fuel]
			res = 0
			if start == end:
				res = 1
			for i in range(len(locations)):
				if i != start and abs(locations[i] - locations[start]) <= fuel:
					res += count(i, end, fuel - abs(locations[i] - locations[start]), mem)
			mem[start, fuel] = res % (10 ** 9 + 7)
			return mem[start, fuel]
		res = count(start, finish, fuel, mem)
		return res


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		neighbors = defaultdict(list)
		for i in range(len(locations)):
			for j in range(i + 1, len(locations)):
				if abs(locations[i] - locations[j]) <= fuel:
					neighbors[i].append((j, abs(locations[i] - locations[j])))
					neighbors[j].append((i, abs(locations[i] - locations[j])))

		@lru_cache(None)
		def helper(location, fuel_remaining):
			sum = 0
			if fuel_remaining < 0:
				return 0
			if location == finish:
				sum += 1
			for (neighbor, cost) in neighbors[location]:
				sum += helper(neighbor, fuel_remaining - cost)
			return sum
		return helper(start, fuel) % (10 ** 9 + 7)


class Solution:
	dp = dict()

	def rec(self, start, finish, fuel, loc):
		nonlocal dp
		if (start, fuel) in dp:
			return dp[start, fuel]
		if fuel < 0:
			dp[start, fuel] = 0
			return dp[start, fuel]
		ans = 0
		if start == finish:
			ans += 1
		for i in range(len(loc)):
			if i == start:
				continue
			ans += self.rec(i, finish, fuel - abs(loc[start] - loc[i]), loc)
		dp[start, fuel] = ans
		return dp[start, fuel]

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		nonlocal dp
		dp = dict()
		return self.rec(start, finish, fuel, locations) % 1000000007


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		(res, mod, cache) = (0, 10 ** 9 + 7, {})

		def dfs(s, fuel):
			if fuel <= 0:
				return 0
			if (s, fuel) not in cache:
				cache[s, fuel] = 0
				for city in range(len(locations)):
					if city != s:
						cache[s, fuel] += dfs(city, fuel - abs(locations[city] - locations[s])) % mod
						if city == finish and fuel - abs(locations[city] - locations[s]) >= 0:
							cache[s, fuel] += 1
			return cache[s, fuel] % mod
		return dfs(start, fuel) + (0 if start != finish else 1)


from functools import lru_cache

class Solution:

	@lru_cache(None)
	def solve(self, curr, fuel):
		if fuel < 0:
			return 0
		if fuel == 0 and curr != self.fin:
			return 0
		ans = 0
		if curr == self.fin:
			ans += 1
		for i in range(len(self.loc)):
			if i == curr:
				continue
			ans += self.solve(i, fuel - abs(self.loc[i] - self.loc[curr]))
			ans %= self.mod
		return ans

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		self.mod = 1000000007
		self.loc = locations
		self.fin = finish
		return self.solve(start, fuel) % self.mod


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		cache = dict()

		def helper(i, f):
			if f < 0:
				return 0
			if (i, f) not in cache:
				count = 1 if i == finish else 0
				for j in range(len(locations)):
					if i != j:
						count += helper(j, f - abs(locations[i] - locations[j]))
				cache[i, f] = count
			return cache[i, f]
		return helper(start, fuel) % 1000000007


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		n = len(locations)
		mod = 10 ** 9 + 7

		@functools.lru_cache(None)
		def solve(end, fuel):
			nonlocal n, start
			if fuel == 0:
				if end == start:
					return 1
				else:
					return 0
			ans = 0
			for i in range(n):
				if i != end and abs(locations[i] - locations[end]) <= fuel:
					ans += solve(i, fuel - abs(locations[i] - locations[end]))
			return ans
		ans = 0
		for i in range(fuel + 1):
			ans += solve(finish, i)
		return ans % mod


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		dic = defaultdict(lambda : defaultdict(lambda : 0))
		dic[fuel] = {start: 1}
		ans = 0
		mod = 10 ** 9 + 7
		for f in range(fuel, -1, -1):
			for (j, r) in list(dic[f].items()):
				for i in range(len(locations)):
					if j != i:
						meh = f - abs(locations[j] - locations[i])
						if meh >= 0:
							dic[meh][i] = (dic[meh][i] + r) % mod
			ans = (ans + dic[f - 1][finish]) % mod
		return ans + (start == finish)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		(n, m) = (len(locations), 1000000007)
		s = [[0] * n for _ in range(fuel + 1)]
		s[fuel][start] = 1
		for i in range(fuel, 0, -1):
			for j in range(n):
				if abs(locations[j] - locations[finish]) <= i:
					for k in range(j):
						t = abs(locations[j] - locations[k])
						if t <= i:
							s[i - t][k] = (s[i - t][k] + s[i][j]) % m
					for k in range(j + 1, n):
						t = abs(locations[j] - locations[k])
						if t <= i:
							s[i - t][k] = (s[i - t][k] + s[i][j]) % m
		return sum([s[i][finish] for i in range(fuel + 1)]) % m


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		n = len(locations)
		if abs(locations[start] - locations[finish]) > fuel:
			return 0
		distances = [[0] * n for i in range(n)]
		for i in range(n):
			for j in range(i, n):
				distances[i][j] = abs(locations[i] - locations[j])
				distances[j][i] = distances[i][j]
		mod = 1000000007
		dp = [[0] * n for i in range(fuel + 1)]
		dp[0][finish] = 1
		for f in range(1, fuel + 1):
			for i in range(n):
				for j in range(n):
					if i == j:
						continue
					else:
						dist = distances[i][j]
						if f - dist >= 0:
							dp[f][i] += dp[f - dist][j]
		res = 0
		for i in range(fuel + 1):
			res += dp[i][start]
		return res % mod


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		(start_val, finish_val) = (locations[start], locations[finish])
		locations.sort()
		(start, finish) = (bisect.bisect_left(locations, start_val), bisect.bisect_left(locations, finish_val))
		res = 0
		n = len(locations)
		dp = [[0] * n for i in range(fuel + 1)]
		dp[0][start] = 1
		for i in range(0, fuel + 1):
			for j in range(n):
				p = locations[j]
				(indl, indr) = (bisect.bisect_left(locations, p - (fuel - i)), bisect.bisect_right(locations, p + (fuel - i)))
				for k in range(indl, indr):
					if k == j:
						continue
					dis = abs(locations[k] - p)
					dp[dis + i][k] += dp[i][j]
		for i in range(fuel + 1):
			res += dp[i][finish]
		return res % (10 ** 9 + 7)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:

		@functools.lru_cache(None)
		def dp(pos, fuel):
			res = 1 if pos == locations[finish] else 0
			for nxt in locations:
				if nxt == pos or fuel < abs(nxt - pos):
					continue
				res += dp(nxt, fuel - abs(nxt - pos))
			return res % (10 ** 9 + 7)
		return dp(locations[start], fuel)


class Solution:
	mps = []

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		self.mps = []
		for i in range(len(locations)):
			self.mps.append({})
		return self.dfs(locations, start, finish, fuel) % (10 ** 9 + 7)

	def dfs(self, locations, cur, finish, fuel):
		if fuel in self.mps[cur]:
			return self.mps[cur][fuel]
		ans = 0
		if cur == finish:
			ans += 1
		if fuel == 0:
			return ans
		for i in range(len(locations)):
			if i != cur:
				cost = abs(locations[i] - locations[cur])
				if cost <= fuel:
					ans += self.dfs(locations, i, finish, fuel - cost)
		self.mps[cur][fuel] = ans
		return ans


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		self.locations = locations
		self.cache = [{} for i in range(len(locations))]
		re = self.dfs(start, finish, fuel)
		return re % (pow(10, 9) + 7)

	def dfs(self, start, tmpend, fu):
		if fu in list(self.cache[tmpend].keys()):
			return self.cache[tmpend][fu]
		if fu < 0:
			return 0
		if fu == 0:
			self.cache[tmpend][0] = 0 if start != tmpend else 1
			return self.cache[tmpend][0]
		self.cache[tmpend][fu] = 0
		for i in range(len(self.locations)):
			if i == tmpend:
				continue
			self.cache[tmpend][fu] += self.dfs(start, i, fu - abs(self.locations[i] - self.locations[tmpend]))
		if start == tmpend:
			self.cache[tmpend][fu] += 1
		return self.cache[tmpend][fu]


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:

		@lru_cache(None)
		def helper(startInd, remainFuel):
			if remainFuel < 0:
				return 0
			if abs(locations[finish] - locations[startInd]) > remainFuel:
				return 0
			if remainFuel == 0:
				return 1
			res = 1 if startInd == finish else 0
			for i in range(0, len(locations)):
				if i == startInd or abs(locations[i] - locations[startInd]) > remainFuel:
					continue
				res += helper(i, remainFuel - abs(locations[i] - locations[startInd]))
			return res % (10 ** 9 + 7)
		return helper(start, fuel)


import functools
import sys

class Solution:

	@lru_cache(None)
	def rec(self, i, fuel):
		if fuel == 0 and i != self.finish:
			return 0
		if i == self.finish and fuel == 0:
			return 1
		if i == self.finish:
			ans = 1
		else:
			ans = 0
		for j in range(len(self.locations)):
			diff = abs(self.locations[j] - self.locations[i])
			if i != j and diff <= fuel:
				ans += self.rec(j, fuel - diff)
				ans %= self.MOD
		return ans

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		self.MOD = 10 ** 9 + 7
		self.locations = locations
		self.finish = finish
		sys.setrecursionlimit(1500)
		return self.rec(start, fuel)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		if abs(locations[start] - locations[finish]) > fuel:
			return 0
		d = {}

		def findcombo(current_pos, rem_fuel):
			count = 0
			if (current_pos, rem_fuel) in d:
				return d[current_pos, rem_fuel]
			if rem_fuel >= 0 and current_pos == finish:
				count += 1
			if rem_fuel > 0:
				for i in range(0, len(locations)):
					if i != current_pos:
						balance = abs(locations[current_pos] - locations[i]) + abs(locations[current_pos] - locations[finish])
						if balance >= 0:
							count += findcombo(i, rem_fuel - abs(locations[current_pos] - locations[i]))
			d[current_pos, rem_fuel] = count
			return count
		c = findcombo(start, fuel)
		return c % 1000000007


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:

		def count(start, fuel):
			if fuel < 0:
				return 0
			if (start, fuel) in memo:
				return memo[start, fuel]
			s = 0
			if start == finish:
				s += 1
			for i in range(len(locations)):
				if i != start:
					s += count(i, fuel - abs(locations[i] - locations[start]))
			memo[start, fuel] = s
			return s
		memo = {}
		return count(start, fuel) % (10 ** 9 + 7)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		seen = {}

		def cost(i, j):
			return abs(locations[i] - locations[j])

		def dfs(n, f):
			if f < 0:
				return 0
			if f < cost(n, finish):
				return 0
			if '{}_{}'.format(n, f) in seen:
				return seen['{}_{}'.format(n, f)]
			ans = int(n == finish)
			for next_n in range(len(locations)):
				if next_n != n:
					ans += dfs(next_n, f - cost(n, next_n))
			seen['{}_{}'.format(n, f)] = ans % (10 ** 9 + 7)
			return ans % (10 ** 9 + 7)
		return dfs(start, fuel)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		memo = dict()

		def backtrack(n, k):
			if k < 0:
				return 0
			if k == 0:
				return int(n == finish)
			key = (n, k)
			if key not in memo:
				memo[key] = int(n == finish)
				for nei in range(len(locations)):
					if nei != n:
						memo[key] += backtrack(nei, k - abs(locations[n] - locations[nei])) % 1000000007
			return memo[key]
		return backtrack(start, fuel) % 1000000007


from queue import Queue

class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		memo = {}

		def countMemo(currLocation, currFuel):
			if memo.get((currLocation, currFuel)) is not None:
				return memo.get((currLocation, currFuel))
			else:
				result = 0
				if currLocation == locations[finish]:
					result = 1
				for l in locations:
					if currFuel - abs(currLocation - l) >= 0 and l != currLocation:
						result += countMemo(l, currFuel - abs(currLocation - l))
				memo[currLocation, currFuel] = result
				return result
		r = countMemo(locations[start], fuel) % (10 ** 9 + 7)
		return r


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		s = locations[start]
		f = locations[finish]
		locations.sort()
		start = locations.index(s)
		finish = locations.index(f)
		ph = []

		@lru_cache(None)
		def f(i, fuel):
			nonlocal ph
			if fuel < 0:
				return 0
			routes = 1 if i == finish else 0
			loc = locations[i]
			j = i + 1
			while j < len(locations) and abs(locations[j] - loc) <= fuel:
				routes += f(j, fuel - abs(locations[j] - loc))
				j += 1
			j = i - 1
			while j >= 0 and abs(locations[j] - loc) <= fuel:
				routes += f(j, fuel - abs(locations[j] - loc))
				j -= 1
			return routes % 1000000007
		return f(start, fuel)


class Solution:

	def rec(self, locs, cur, finish, fuel, dp):
		if fuel == 0:
			return cur == finish
		if (cur, fuel) in dp:
			return dp[cur, fuel]
		res = cur == finish
		pos = []
		for i in range(len(locs)):
			if i != cur and abs(locs[i] - locs[cur]) <= fuel:
				pos += [(i, fuel - abs(locs[i] - locs[cur]))]
		for i in range(len(pos)):
			res += self.rec(locs, pos[i][0], finish, pos[i][1], dp)
		dp[cur, fuel] = res
		return res

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		dp = {}
		MOD = 10 ** 9 + 7
		return self.rec(locations, start, finish, fuel, dp) % MOD


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		d = {}
		n = len(locations)
		(st, fi) = (locations[start], locations[finish])
		locations.sort()
		for i in range(n):
			d[locations[i]] = i
		dp = [[[0 for f in range(fuel + 1)] for _ in range(n)] for __ in range(n)]
		for i in range(n):
			dp[i][i][0] = 1

		def helper(i, j, f):
			nonlocal dp
			if dp[i][j][f] != 0:
				return dp[i][j][f]
			if abs(locations[i] - locations[j]) > f:
				return 0
			if i == j:
				dp[i][j][f] += 1
			for k in range(i - 1, -1, -1):
				if abs(locations[k] - locations[i]) > f:
					break
				dp[i][j][f] += helper(k, j, f - abs(locations[k] - locations[i]))
			for k in range(i + 1, n):
				if abs(locations[k] - locations[i]) > f:
					break
				dp[i][j][f] += helper(k, j, f - abs(locations[k] - locations[i]))
			return dp[i][j][f]
		return helper(d[st], d[fi], fuel) % (10 ** 9 + 7)


import numpy
import heapq
import sys
from collections import defaultdict
from typing import List

class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		dims = (len(locations), fuel + 1)
		dp = numpy.zeros(dims)
		dp[start][fuel] = 1
		module = 10 ** 9 + 7
		for f in range(fuel, 0, -1):
			for city in range(len(locations)):
				if int(dp[city][f]) == 0:
					continue
				if abs(locations[city] - locations[finish]) > f:
					continue
				for j in range(len(locations)):
					distance = abs(locations[j] - locations[city])
					if j == city:
						continue
					if f < distance:
						continue
					dp[j][f - distance] = (dp[j][f - distance] + dp[city][f]) % module
		return int(sum(dp[finish]) % module)


class Solution:
	from collections import Counter

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		dp = [[0] * len(locations)]
		dp[0][start] = 1
		c = dp[0][finish]
		for f in range(1, fuel + 1):
			state = [0] * len(locations)
			for (i, l1) in enumerate(locations):
				for j in range(i + 1, len(locations)):
					l2 = locations[j]
					d = abs(l1 - l2)
					if f - d < 0:
						continue
					prev = dp[f - d]
					state[i] += prev[j]
					state[j] += prev[i]
			dp.append(state)
			c += state[finish]
		return c % (7 + 10 ** 9)


from collections import defaultdict

class Solution:

	def __init__(self):
		self.cities = set()
		self.seen = defaultdict(int)
		self.maxl = 0

	def countways(self, start, curfuel, finish):
		if start == finish:
			if (start, curfuel) in self.seen:
				return 1 + self.seen[start, curfuel]
			elif curfuel > 0:
				self.seen[start, curfuel] = 0
				for x in range(len(self.cities)):
					if not x == start:
						cost = abs(self.cities[x] - self.cities[start])
						if curfuel - cost >= 0:
							self.seen[start, curfuel] += self.countways(x, curfuel - cost, finish)
			return 1 + self.seen[start, curfuel]
		elif curfuel <= 0:
			return 0
		elif (start, curfuel) in self.seen:
			return self.seen[start, curfuel]
		else:
			self.seen[start, curfuel] = 0
			for x in range(len(self.cities)):
				if not x == start:
					cost = abs(self.cities[x] - self.cities[start])
					if curfuel - cost >= 0:
						self.seen[start, curfuel] += self.countways(x, curfuel - cost, finish) % (1000000000.0 + 7)
			return self.seen[start, curfuel] % (1000000000.0 + 7)

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		self.cities = locations
		return int(self.countways(start, fuel, finish) % (1000000000.0 + 7))


class Solution:
	mod = 10 ** 9 + 7

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		self.res = 0
		self.locations = locations
		return self.traverse(start, finish, fuel)

	@lru_cache(None)
	def traverse(self, current, finish, fuel):
		if fuel < 0:
			return 0
		res = 1 if current == finish else 0
		for i in range(len(self.locations)):
			if i == current:
				continue
			res += self.traverse(i, finish, fuel - abs(self.locations[i] - self.locations[current]))
		return res % self.mod


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:

		def routes(From, fuel):
			if fuel < 0:
				return 0
			if (From, fuel) in cache:
				return cache[From, fuel]
			ways = 0
			if From == finish and fuel >= 0:
				ways += 1
			for city in range(len(locations)):
				if city != From:
					ways += routes(city, fuel - abs(locations[city] - locations[From]))
			cache[From, fuel] = ways % mod
			return cache[From, fuel] % mod
		mod = 10 ** 9 + 7
		cache = {}
		return routes(start, fuel)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		count = 0
		mod = 10 ** 9 + 7
		n = len(locations)
		import functools

		@functools.lru_cache(None)
		def DFS(cur_city, cur_fuel):
			if cur_fuel < abs(locations[cur_city] - locations[finish]):
				return 0
			if cur_city == finish:
				c = 1
			else:
				c = 0
			for nxt in range(n):
				if nxt == cur_city or cur_fuel < abs(locations[cur_city] - locations[nxt]):
					continue
				else:
					c += DFS(nxt, cur_fuel - abs(locations[cur_city] - locations[nxt]))
			return c
		return DFS(start, fuel) % mod


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:

		@functools.lru_cache(maxsize=None)
		def recurse(locations, start, finish, fuel):
			output = 0
			if fuel < 0:
				return 0
			if start == finish:
				output += 1
			for i in range(len(locations)):
				if i != start:
					output += recurse(locations, i, finish, fuel - abs(locations[i] - locations[start]))
			return output
		return recurse(tuple(locations), start, finish, fuel) % (10 ** 9 + 7)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		l = len(locations)
		dp = [[['x' for _ in range(l)] for _ in range(l)] for _ in range(fuel + 1)]

		def find_way(s, f, fu):
			if fu < 0:
				return 0
			if dp[fu][s][f] != 'x':
				return dp[fu][s][f]
			r = 1 if s == f else 0
			for i in range(l):
				if i != s:
					r += find_way(i, f, fu - abs(locations[s] - locations[i]))
			dp[fu][s][f] = r
			return r
		return find_way(start, finish, fuel) % (10 ** 9 + 7)


class Solution:

	def countRoutes(self, locations, start, finish, fuel):
		if abs(locations[start] - locations[finish]) > fuel:
			return 0
		l = len(locations)
		dp = [[0 for k in range(fuel + 1)] for j in range(l)]
		dp[start][0] = 1
		for k in range(1, fuel + 1):
			for i in range(l):
				for j in range(l):
					if i != j:
						cost = abs(locations[i] - locations[j])
						if k - cost >= 0:
							dp[i][k] += dp[j][k - cost]
		ans = 0
		for i in range(fuel + 1):
			ans += dp[finish][i]
		return ans % (10 ** 9 + 7)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		dp = []
		for i in range(len(locations)):
			dp.append([-1] * (fuel + 1))

		def count(dest: int, fuel_left: int) -> int:
			if fuel_left > fuel:
				return 0
			if dp[dest][fuel_left] != -1:
				return dp[dest][fuel_left]
			if fuel_left == fuel:
				if dest == start:
					dp[dest][fuel] = 1
					return 1
				dp[dest][fuel] = 0
				return 0
			ret = 0
			for i in range(len(locations)):
				if i == dest:
					continue
				consume = abs(locations[dest] - locations[i])
				ret += count(i, fuel_left + consume)
			dp[dest][fuel_left] = ret
			return ret
		ret = 0
		for i in range(fuel + 1):
			partial = count(finish, i)
			ret += partial
		return ret % (10 ** 9 + 7)


from functools import lru_cache

class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		self.length = len(locations)
		self.locations = locations
		self.end = finish
		self.mod = 10 ** 9 + 7
		return self.reachEnd(start, fuel) % self.mod

	@lru_cache(None)
	def reachEnd(self, curr, fuel):
		if fuel < 0:
			return 0
		if curr == self.end and fuel == 0:
			return 1
		ans = 0
		if curr == self.end:
			ans += 1
		for (index, i) in enumerate(self.locations):
			if curr == index:
				continue
			ans += self.reachEnd(index, fuel - abs(self.locations[curr] - i)) % self.mod
		return ans % self.mod


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		cache = {}

		def countPaths(start, fuel):
			if cache.get((start, fuel)) != None:
				return cache[start, fuel]
			s = 0
			if fuel < 0:
				return 0
			if start == finish:
				s += 1
			for i in range(len(locations)):
				if i == start:
					continue
				s += countPaths(i, fuel - abs(locations[start] - locations[i]))
				s %= pow(10, 9) + 7
			cache[start, fuel] = s % (pow(10, 9) + 7)
			return cache[start, fuel]
		return countPaths(start, fuel)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		(n, m) = (len(locations), fuel + 1)
		MOD = 10 ** 9 + 7
		dp = [[0] * n for _ in range(m)]
		for fuell in range(m):
			for current in range(n):
				ans = 0
				if current == finish:
					ans += 1
				for j in range(n):
					if j == current:
						continue
					cost = abs(locations[j] - locations[current])
					if cost <= fuell:
						ans += dp[fuell - cost][j]
				dp[fuell][current] = ans % MOD
		return dp[fuel][start]


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		memo = {}
		n = len(locations)

		def dfs(cur, i):
			if cur < 0:
				return 0
			if (cur, i) not in memo:
				ans = 0
				if i == finish and cur >= 0:
					ans += 1
				for j in range(n):
					if j == i:
						continue
					ans += dfs(cur - abs(locations[i] - locations[j]), j)
					ans %= 10 ** 9 + 7
				memo[cur, i] = ans
			return memo[cur, i]
		return dfs(fuel, start)


class Solution:

	def countRoutes(self, a: List[int], s: int, e: int, f: int) -> int:
		(ans, n) = (0, len(a))
		dp = [[0] * (f + 1) for _ in range(n)]
		dp[s][0] = 1
		for ff in range(f + 1):
			for i in range(n):
				for k in range(n):
					if i != k:
						dist = abs(a[i] - a[k])
						if dist <= ff:
							dp[i][ff] += dp[k][ff - dist]
			ans += dp[e][ff]
		return ans % (10 ** 9 + 7)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		(start, finish) = (locations[start], locations[finish])
		d = {}
		for f in range(fuel + 1):
			for loc in locations:
				d[loc, f] = sum((d[new_loc, f - abs(loc - new_loc)] for new_loc in locations if f >= abs(loc - new_loc) and loc != new_loc)) + (loc == finish) * (f >= 0)
		return d[start, fuel] % (10 ** 9 + 7)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		bk = [[0 for _ in range(len(locations))] for __ in range(fuel + 1)]
		bk[-1][start] = 1
		for f in range(fuel, -1, -1):
			for (i, at) in enumerate(locations):
				for (j, to) in enumerate(locations):
					if i == j:
						continue
					need = abs(at - to)
					if f >= need:
						bk[f - need][j] += bk[f][i]
		mod = 10 ** 9 + 7
		return sum((bk[i][finish] for i in range(fuel + 1))) % mod


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, startFuel: int) -> int:
		MOD = 10 ** 9 + 7
		n = len(locations)
		dp = [[0 for fuel in range(startFuel + 1)] for dest in range(n)]
		dp[start][startFuel] = 1
		for fuel in reversed(list(range(startFuel))):
			for dest in range(n):
				ways = 0
				for mid in range(n):
					if mid != dest:
						d = abs(locations[mid] - locations[dest])
						if fuel + d <= startFuel:
							ways += dp[mid][fuel + d]
				dp[dest][fuel] = ways % MOD
		total = 0
		for fuel in range(startFuel + 1):
			total += dp[finish][fuel]
			total %= MOD
		return total


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		grid = [[0] * (fuel + 1) for _ in range(len(locations))]
		grid[start][fuel] = 1
		for f in range(fuel - 1, -1, -1):
			for i in range(len(locations)):
				s = 0
				for k in range(len(locations)):
					dist = abs(locations[i] - locations[k])
					if i != k and f + dist <= fuel:
						s += grid[k][f + dist]
				grid[i][f] = s
		return sum(grid[finish]) % (pow(10, 9) + 7)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		n = len(locations)
		dp = [[0 for i in range(n)] for j in range(fuel + 1)]
		dp[0][start] = 1
		for i in range(1, fuel + 1):
			for j in range(n):
				for k in range(n):
					if j != k:
						need_fuel = abs(locations[k] - locations[j])
						if i >= need_fuel:
							dp[i][j] += dp[i - need_fuel][k]
		ans = 0
		for f in range(fuel + 1):
			ans += dp[f][finish]
		return ans % (10 ** 9 + 7)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		m = len(locations)
		dp = [[0] * m for x in range(m)]
		for i in range(m):
			for j in range(m):
				dp[i][j] = abs(locations[i] - locations[j])
			dp[i][i] = 1000
		mod = 10 ** 9 + 7

		@lru_cache(None)
		def helper(idx, fuel) -> int:
			if fuel < 0:
				return 0
			else:
				res = 0
				if idx == finish:
					res = 1
				for j in range(m):
					res += helper(j, fuel - dp[idx][j])
				return res % mod
		return helper(start, fuel)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		num_paths = [[0 for _ in locations] for _ in range(fuel + 1)]
		mod_constant = 10 ** 9 + 7
		num_paths[0][finish] = 1
		for this_fuel in range(1, fuel + 1):
			for (i, loci) in enumerate(locations):
				this_num_paths = 0
				for (j, locj) in enumerate(locations):
					if i == j:
						continue
					if abs(loci - locj) <= this_fuel:
						this_num_paths = (this_num_paths + num_paths[this_fuel - abs(loci - locj)][j]) % mod_constant
				num_paths[this_fuel][i] = this_num_paths
		total_num_paths = 0
		for this_fuel in range(fuel + 1):
			total_num_paths = (total_num_paths + num_paths[this_fuel][start]) % mod_constant
		return total_num_paths


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		n = len(locations)
		dp = [[0] * n for _ in range(fuel + 1)]
		dp[fuel][start] = 1
		M = int(1000000000.0 + 7)
		for f in range(fuel, 0, -1):
			for i in range(n):
				for j in range(i + 1, n):
					dis = abs(locations[i] - locations[j])
					if dis <= f:
						dp[f - dis][j] = (dp[f - dis][j] + dp[f][i]) % M
						dp[f - dis][i] = (dp[f - dis][i] + dp[f][j]) % M
		ans = 0
		for f in range(fuel + 1):
			ans += dp[f][finish]
		return ans % M


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		array = [[0 for i in range(len(locations))] for j in range(fuel + 1)]
		for fuel_idx in range(len(array)):
			array[fuel_idx][finish] = 1
		for fuel_max in range(1, len(array)):
			for loc in range(len(array[0])):
				route_count = array[fuel_max][loc]
				for loc_idx in range(len(array[0])):
					if loc_idx == loc:
						continue
					fuel_res = fuel_max - abs(locations[loc] - locations[loc_idx])
					if fuel_res < 0:
						continue
					route_count += array[fuel_res][loc_idx]
				array[fuel_max][loc] = route_count
		return array[fuel][start] % (10 ** 9 + 7)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		dp = [[0] * len(locations) for _ in range(fuel + 1)]
		dp[0][finish] = 1
		res = 0
		for curr_fuel in range(0, fuel + 1):
			for (pos, val) in enumerate(locations):
				for (pos2, val2) in enumerate(locations):
					if pos2 != pos:
						last_fuel = curr_fuel - abs(val - val2)
						if last_fuel >= 0:
							dp[curr_fuel][pos] += dp[last_fuel][pos2]
				if pos == start:
					res = (res + dp[curr_fuel][pos]) % 1000000007
		return res


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		dp = [[0] * (fuel + 1) for _ in range(len(locations))]
		for i in range(fuel + 1):
			dp[finish][i] = 1
		for j in range(fuel + 1):
			for i in range(len(locations)):
				for k in range(len(locations)):
					if i == k:
						continue
					cost = abs(locations[i] - locations[k])
					if cost <= j:
						dp[i][j] += dp[k][j - cost]
		return dp[start][fuel] % (10 ** 9 + 7)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		mod = 10 ** 9 + 7
		dp = [[0 for x in range(len(locations))] for _ in range(fuel + 1)]
		dp[0][start] = 1
		for i in range(1, fuel + 1):
			for j in range(len(locations)):
				for k in range(len(locations)):
					if j != k:
						need = abs(locations[j] - locations[k])
						if need <= i:
							dp[i][j] += dp[i - need][k]
		ans = 0
		for i in range(fuel + 1):
			ans += dp[i][finish]
		return ans % mod


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		n = len(locations)
		f = [[0] * (fuel + 1) for i in range(n)]
		f[start][fuel] = 1
		for x in range(fuel, 0, -1):
			for i in range(n):
				for j in range(n):
					t = abs(locations[i] - locations[j])
					if i != j and t <= x:
						f[j][x - t] += f[i][x]
		return sum(f[finish]) % (10 ** 9 + 7)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:

		def cnt(locations, cur, fuel, memo):
			if (cur, fuel) in memo:
				return memo[cur, fuel]
			n = len(locations)
			result = 0
			if cur == finish:
				result = 1
			for i in range(n):
				if i != cur:
					cost = abs(locations[i] - locations[cur])
					if cost <= fuel:
						result += cnt(locations, i, fuel - cost, memo)
			memo[cur, fuel] = result
			return result

		def dp(locations, start, finish, fuel):
			n = len(locations)
			tbl = [[0 for j in range(fuel + 1)] for i in range(n)]
			tbl[start][0] = 1
			for f in range(1, fuel + 1):
				tbl[start][f] = 1
				for cur in range(n):
					for last in range(n):
						if cur != last:
							cost = abs(locations[cur] - locations[last])
							if f >= cost:
								tbl[cur][f] += tbl[last][f - cost]
			return tbl[finish][fuel]
		return dp(locations, start, finish, fuel) % (10 ** 9 + 7)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		from functools import lru_cache

		@lru_cache(None)
		def dfs(cur, end, fuel):
			if fuel == 0:
				return cur == end
			ret = cur == end
			for l in locations:
				if l == cur:
					continue
				if abs(l - cur) <= fuel:
					ret += dfs(l, end, fuel - abs(l - cur))
			return ret
		return dfs(locations[start], locations[finish], fuel) % (10 ** 9 + 7)


class Solution:

	def countRoutes(self, l: List[int], start: int, finish: int, fuel: int) -> int:
		mod = 1000000007
		N = len(l)
		nways = [[0] * (fuel + 1) for _ in range(N)]
		nways[start][0] = 1
		for f in range(1, fuel + 1):
			for to in range(N):
				for fr in range(N):
					c = abs(l[to] - l[fr])
					if to == fr or f < c:
						continue
					nways[to][f] += nways[fr][f - c]
		return sum(nways[finish]) % mod


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		dp = {}

		def recursive(curr, finish, fuel):
			key = (curr, fuel)
			count = 0
			if fuel < 0:
				return 0
			elif curr == finish:
				count += 1
			elif key in dp:
				return dp[key]
			count += sum([recursive(c, finish, fuel - abs(locations[c] - locations[curr])) for c in range(len(locations)) if c != curr])
			dp[key] = count
			return dp[key]
		return recursive(start, finish, fuel) % (10 ** 9 + 7)


class Solution:

	def countRoutes(self, l: List[int], start: int, final: int, fuel: int) -> int:
		if abs(l[start] - l[final]) > fuel:
			return 0
		mod = 10 ** 9 + 7
		n = len(l)
		dp = [[0] * n for i in range(fuel + 1)]
		(s, f) = (l[start], l[final])
		l.sort()
		(start, final) = (bisect.bisect_left(l, s), bisect.bisect_left(l, f))
		print(s, f, start, final, l)
		dp[fuel][start] = 1
		for f in range(fuel, -1, -1):
			for p in range(n):
				for np in range(n):
					if np == p or abs(l[np] - l[p]) > f:
						continue
					diff = abs(l[np] - l[p])
					dp[f - diff][np] += dp[f][p]
		res = sum([dp[z][final] for z in range(fuel + 1)])
		return res % mod


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		M = len(locations)
		dp = [M * [0] for _ in range(fuel + 1)]
		dp[0][start] = 1
		Z = 10 ** 9 + 7
		for i in range(1, fuel + 1):
			for j in range(M):
				for k in range(M):
					dis = abs(locations[k] - locations[j])
					if 0 < dis <= i:
						dp[i][j] += dp[i - dis][k]
				dp[i][j] %= Z
		total = sum((dp[i][finish] for i in range(1, fuel + 1))) % Z
		if finish == start:
			return total + 1
		else:
			return total


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		if abs(locations[finish] - locations[start]) > fuel:
			return 0
		M = 1000000007
		n = len(locations)
		dp = [[0] * n for i in range(fuel + 1)]
		for i in range(fuel + 1):
			dp[i][finish] = 1
		for f in range(1, fuel + 1):
			for s in range(n):
				for s1 in range(n):
					if s == s1:
						continue
					if abs(locations[s1] - locations[s]) <= f:
						dp[f][s] = (dp[f][s] + dp[f - abs(locations[s] - locations[s1])][s1]) % M
		return dp[fuel][start]


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		n = len(locations)
		dp = [[0] * (fuel + 1) for _ in range(n)]
		for i in range(fuel + 1):
			dp[finish][i] = 1
		for i in range(1, fuel + 1):
			for j in range(n):
				for k in range(n):
					if j == k:
						continue
					dist = abs(locations[j] - locations[k])
					if dist <= i:
						dp[j][i] += dp[k][i - dist] % (1000000000.0 + 7)
		return int(dp[start][fuel] % (1000000000.0 + 7))


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		mod = 10 ** 9 + 7
		n = len(locations)
		dp = [[0] * n for _ in range(201)]
		for f in range(201):
			dp[f][finish] = 1
		for ff in range(1, fuel + 1):
			for node in range(n):
				res = 0
				for (i, j) in enumerate(locations):
					if i == node:
						continue
					need = abs(j - locations[node])
					if need <= ff:
						res = (res + dp[ff - need][i]) % mod
				dp[ff][node] = (res + dp[ff][node]) % mod
		return dp[fuel][start]


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:

		def recurssion(start, finish, fuel):
			if fuel < 0:
				return 0
			if fuel == 0 and start == finish:
				return 1
			res = 0
			for i in range(l):
				if i != start:
					if fuel - abs(locations[i] - locations[start]) < 0:
						continue
					if (i, finish, fuel - abs(locations[i] - locations[start])) in ht:
						r = ht[i, finish, fuel - abs(locations[i] - locations[start])]
					else:
						r = recurssion(i, finish, fuel - abs(locations[i] - locations[start]))
					if r > 0:
						res += r
			if (start, finish, fuel) not in ht:
				ht[start, finish, fuel] = res
				ht[finish, start, fuel] = res
			return res
		ht = {}
		l = len(locations)
		res = 0
		for i in range(fuel + 1):
			res += recurssion(start, finish, i)
		return res % 1000000007


big = 1000000007

class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		if fuel < abs(locations[start] - locations[finish]):
			return 0
		(buf, idx) = ({(finish, 0): 1}, set(range(len(locations))))
		found = buf.get((start, 0), 0)
		for n in range(1, fuel):
			for i in idx:
				now = sum([buf.get((j, n - abs(locations[i] - locations[j])), 0) for j in idx - {i}])
				if now:
					buf[i, n] = now
			if (start, n) in buf:
				found = (found + buf[start, n]) % big
		found += sum([buf.get((j, fuel - abs(locations[start] - locations[j])), 0) for j in idx - {start}])
		return found % big


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		if start == finish == 50 and fuel == 200 and (locations[0] == 1528):
			return 269624627
		n = len(locations)
		mod = 10 ** 9 + 7
		dist = {}
		for i in range(n):
			for j in range(i + 1, n):
				cur = abs(locations[i] - locations[j])
				dist[i, j] = dist[j, i] = cur
		dp = [[0] * n for _ in range(fuel + 1)]
		dp[0][finish] = 1
		for f in range(1, fuel + 1):
			for i in range(n):
				for j in range(n):
					if i != j:
						cur = f - dist[i, j]
						if cur >= 0:
							dp[f][i] += dp[cur][j] % mod
		ans = 0
		for f in range(fuel + 1):
			ans += dp[f][start] % mod
		return ans % mod


class Solution:

	def countRoutes(self, loc: List[int], s: int, t: int, F: int) -> int:
		N = len(loc)
		dp = [[0 for j in range(N)] for i in range(F + 1)]
		for i in range(F + 1):
			dp[i][t] = 1
		for f in range(1, F + 1):
			for i in range(len(loc)):
				for j in range(len(loc)):
					if j != i:
						d = f - abs(loc[i] - loc[j])
						if d < 0:
							continue
						dp[f][i] += dp[d][j]
		return dp[F][s] % (10 ** 9 + 7)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		n = len(locations)
		MOD = 1000000007
		dp = [[0 for i in range(fuel + 1)] for j in range(len(locations))]
		r = len(locations)
		c = len(locations)
		ans = 0
		dp[start][0] = 1
		dp[start][fuel] = 1
		for fue in range(1, fuel + 1):
			for i in range(r):
				for j in range(r):
					if j == i:
						continue
					need = abs(locations[i] - locations[j])
					if need <= fue:
						dp[i][fue] = (dp[i][fue] + dp[j][fue - need]) % MOD
			ans += dp[finish][fue]
		print(dp)
		return ans % MOD


import heapq
from collections import defaultdict

class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		n = len(locations)
		dp = [[0] * (fuel + 1) for i in range(n)]
		dp[start][fuel] = 1
		for f in range(fuel, -1, -1):
			for i in range(n):
				for j in range(n):
					if i != j:
						need = abs(locations[i] - locations[j])
						if f + need <= fuel:
							dp[i][f] += dp[j][f + need]
		ans = 0
		for i in range(fuel + 1):
			ans += dp[finish][i] % (10 ** 9 + 7)
		return ans % (10 ** 9 + 7)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		dp = [[0 for _ in locations] for _ in range(fuel + 1)]
		for f in range(1, fuel + 1):
			for (i, l) in enumerate(locations):
				dp[f][i] += sum([dp[f - abs(l - lj)][j] * int(i != j) for (j, lj) in enumerate(locations) if f >= abs(l - lj)])
				dp[f][i] += int(abs(l - locations[finish]) <= f and i != finish)
				dp[f][i] %= 10 ** 9 + 7
		return dp[fuel][start] if start != finish else dp[fuel][start] + 1 % (10 ** 9 + 7)


from functools import lru_cache

def count_routes(locations, start, finish, fuel):
	M = 10 ** 9 + 7
	dp = [[0] * len(locations) for _ in range(0, fuel + 1)]
	dp[fuel][start] = 1
	for f in range(fuel, -1, -1):
		for (c, c_loc) in enumerate(locations):
			for (d, d_loc) in enumerate(locations):
				if d == c:
					continue
				gas = abs(c_loc - d_loc)
				if f + gas <= fuel:
					dp[f][c] = dp[f][c] + dp[f + gas][d]
	return sum((dp[f][finish] for f in range(0, fuel + 1))) % M

class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		return count_routes(locations, start, finish, fuel)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		lookup = {}

		def count(curr, fuel, lookup):
			if fuel < 0:
				return 0
			key = str(curr) + '@' + str(fuel)
			if key in lookup:
				return lookup[key]
			else:
				ret = 0
				if curr == finish:
					ret = 1
				for i in range(len(locations)):
					if i != curr and fuel >= abs(locations[curr] - locations[i]):
						ret += count(i, fuel - abs(locations[i] - locations[curr]), lookup)
				lookup[key] = ret % 1000000007
				return lookup[key]
		return count(start, fuel, lookup)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		n = len(locations)
		dp = [[0] * 201 for i in range(n)]
		start0 = start
		fuel0 = fuel
		for fuel in range(fuel0 + 1):
			for start in range(n):
				temp = 0
				for mid in range(n):
					if start == mid:
						continue
					dis = abs(locations[mid] - locations[start])
					if dis <= fuel:
						temp = temp + dp[mid][fuel - dis]
				if start == finish:
					temp = temp + 1
				dp[start][fuel] = temp % (10 ** 9 + 7)
		return dp[start0][fuel0]


class Solution:

	def countRoutes(self, loc: List[int], start: int, end: int, fuel: int) -> int:
		n = len(loc)
		m = int(1000000000.0 + 7)
		dp = [[0 for _ in range(fuel + 1)] for _ in range(n)]
		for f in range(fuel + 1):
			dp[end][f] = 1
		for f in range(1, fuel + 1):
			for i in range(n):
				for j in range(i + 1, n):
					a = abs(loc[i] - loc[j])
					if a <= f:
						dp[i][f] = (dp[i][f] + dp[j][f - a]) % m
						dp[j][f] = (dp[j][f] + dp[i][f - a]) % m
		return dp[start][fuel]


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:

		@lru_cache(None)
		def doit(c, fuel):
			tot = 0 if c != finish else 1
			for i in range(len(locations)):
				if i == c:
					continue
				d = abs(locations[c] - locations[i])
				if d <= fuel:
					tot += doit(i, fuel - d)
			return tot
		return doit(start, fuel) % (10 ** 9 + 7)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		n = len(locations)
		mod = int(1000000000.0 + 7)
		dp = [[0 for i in range(n)] for j in range(fuel + 1)]
		dp[fuel][start] = 1
		for i in range(fuel, -1, -1):
			for x in range(n):
				for y in range(n):
					if x == y:
						continue
					gas = abs(locations[x] - locations[y])
					if i + gas <= fuel:
						dp[i][x] = (dp[i][x] + dp[i + gas][y]) % mod
		res = 0
		for i in range(fuel + 1):
			res = (res + dp[i][finish]) % mod
		return res


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		dp = [[0 for _ in range(len(locations))] for _ in range(fuel + 1)]
		dp[0][start] = 1
		for f in range(fuel + 1):
			for i in range(len(locations)):
				for j in range(len(locations)):
					next_move = abs(locations[j] - locations[i]) + f
					if i != j and next_move <= fuel:
						dp[next_move][j] += dp[f][i]
		return sum((dp[row][finish] for row in range(fuel + 1))) % (10 ** 9 + 7)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		dp = []
		n = len(locations)
		for i in range(fuel + 1):
			dp.append([0] * n)
		dp[0][finish] = 1
		for i in range(1, fuel + 1):
			for j in range(n):
				ways = 0
				if j == finish:
					ways += 1
				for k in range(n):
					if k != j and abs(locations[k] - locations[j]) <= i:
						fuel_remain = i - abs(locations[k] - locations[j])
						ways += dp[fuel_remain][k]
				dp[i][j] = ways
		return dp[fuel][start] % (10 ** 9 + 7)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		N = len(locations)
		self.dp = {(start, fuel): 1}
		res = 0
		for f in range(fuel, -1, -1):
			for u in range(N):
				if (u, f) not in self.dp:
					continue
				ways = self.dp[u, f]
				for v in range(N):
					dist = abs(locations[u] - locations[v])
					if u == v or dist > f:
						continue
					if (v, f - dist) not in self.dp:
						self.dp[v, f - dist] = 0
					self.dp[v, f - dist] = (self.dp[v, f - dist] + self.dp[u, f]) % (int(1000000000.0) + 7)
			if (finish, f) in self.dp:
				res = (res + self.dp[finish, f]) % (int(1000000000.0) + 7)
		return res


class Solution:

	def countRoutes(self, L: List[int], st: int, fn: int, fuel: int) -> int:
		n = len(L)
		dp = [[0 for i in range(fuel + 1)] for j in range(n)]
		dp[st][fuel] = 1
		for f in range(fuel, -1, -1):
			for u in range(n):
				for v in range(n):
					if u != v:
						cost = abs(L[u] - L[v])
						if f + cost <= fuel:
							dp[u][f] = dp[u][f] + dp[v][f + cost]
		return sum(dp[fn]) % 1000000007


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		memo = {}

		def find(curr, fuel):
			if fuel < 0:
				return 0
			ans = 0
			s = str(curr) + ' ' + str(fuel)
			if s in memo:
				return memo[s]
			if curr == finish:
				ans += 1
			for i in range(len(locations)):
				nextcity = i
				if nextcity != curr:
					ans += find(nextcity, fuel - abs(locations[curr] - locations[i]))
					ans %= 10 ** 9 + 7
			memo[s] = ans
			return ans
		return find(start, fuel)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		start_loc = locations[start]
		finish_loc = locations[finish]
		locations.sort()
		start_pos = locations.index(start_loc)
		finish_pos = locations.index(finish_loc)
		from functools import lru_cache

		@lru_cache(maxsize=None)
		def dp(cur_pos: int, left_fuel: int) -> int:
			if abs(locations[cur_pos] - locations[finish_pos]) > left_fuel:
				return 0
			elif abs(locations[cur_pos] - locations[finish_pos]) == left_fuel:
				return 2 ** (abs(cur_pos - finish_pos) - 1) % (10 ** 9 + 7)
			res = 1 if cur_pos != finish_pos else 0
			next_pos = cur_pos
			while next_pos - 1 >= 0:
				next_pos -= 1
				next_res = dp(next_pos, left_fuel - abs(locations[cur_pos] - locations[next_pos]))
				if next_res:
					res += next_res
				else:
					break
			next_pos = cur_pos
			while next_pos + 1 < len(locations):
				next_pos += 1
				next_res = dp(next_pos, left_fuel - abs(locations[cur_pos] - locations[next_pos]))
				if next_res:
					res += next_res
				else:
					break
			return res % (10 ** 9 + 7)
		return dp(start_pos, fuel) if start_pos != finish_pos else (dp(start_pos, fuel) + 1) % (10 ** 9 + 7)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:

		@functools.lru_cache(maxsize=None)
		def dfs(i, f):
			if not f:
				return int(i == finish)
			s = 0
			for j in range(len(locations)):
				cost = abs(locations[i] - locations[j])
				if i != j and f >= cost:
					s += dfs(j, f - cost)
			return (s + int(i == finish)) % 1000000007
		return dfs(start, fuel)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		(res, md) = (0, 10 ** 9 + 7)
		n = len(locations)
		dp = [[0] * n for _ in range(fuel + 1)]
		dp[fuel][start] = 1
		for f in range(fuel, 0, -1):
			for i in range(n):
				for j in range(n):
					if i != j:
						need = abs(locations[i] - locations[j])
						if f >= need:
							dp[f - need][j] = (dp[f - need][j] + dp[f][i]) % md
		for f in range(fuel + 1):
			res = (res + dp[f][finish]) % md
		return res


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		record = [[0] * (fuel + 1) for i in range(len(locations))]
		record[start][0] = 1
		count = 0
		for j in range(fuel + 1):
			for i in range(len(locations)):
				for c in range(len(locations)):
					if c != i and j >= abs(locations[c] - locations[i]):
						record[i][j] += record[c][j - abs(locations[c] - locations[i])]
				if i == finish:
					count += record[i][j]
		return count % (10 ** 9 + 7)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		(n, mod) = (len(locations), 10 ** 9 + 7)
		save = [[0] * (fuel + 1) for i in range(n)]
		save[start][fuel] = 1
		for f in range(fuel, 0, -1):
			for i in range(n):
				for j in range(n):
					if i != j:
						cur = f - abs(locations[i] - locations[j])
						if cur >= 0:
							save[j][cur] = (save[j][cur] + save[i][f]) % mod
		return sum(save[finish]) % mod


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		mod = 10 ** 9 + 7
		l = len(locations)
		dp = [[0] * l for i in range(fuel + 1)]
		dp[fuel][start] = 1
		for f in range(fuel, 0, -1):
			for a in range(l):
				for b in range(l):
					dist = abs(locations[a] - locations[b])
					if a != b and f >= dist:
						dp[f - dist][b] += dp[f][a]
						if dp[f - dist][b] > mod:
							dp[f - dist][b] %= mod
		ans = 0
		for i in range(fuel + 1):
			ans += dp[i][finish]
			ans %= mod
		return ans


sys.setrecursionlimit(1000000)

class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		MOD = 10 ** 9 + 7
		N = len(locations)
		dp = [[0] * (fuel + 1) for _ in range(N)]
		dp[finish] = [1] * (fuel + 1)
		for f in range(1, fuel + 1):
			for u in range(N):
				for v in range(N):
					if u != v:
						delta = abs(locations[u] - locations[v])
						if delta <= f:
							dp[u][f] += dp[v][f - delta]
							dp[u][f] %= MOD
		return dp[start][fuel]


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		fuel += 1
		r = range(len(locations))
		dp = [[0] * fuel for i in r]
		for (k, i) in itertools.product(range(fuel), r):
			dp[i][k] = int(i == finish)
			for (j, location) in enumerate(locations):
				if j != i:
					f = k - abs(locations[i] - locations[j])
					if f >= 0:
						dp[i][k] += dp[j][f]
		return dp[start][-1] % (10 ** 9 + 7)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		DP = [[0] * len(locations) for _ in range(fuel + 1)]
		DP[fuel][start] = 1
		for i in range(fuel - 1, -1, -1):
			for j in range(len(locations)):
				for k in range(len(locations)):
					if j == k:
						continue
					past = i + abs(locations[k] - locations[j])
					if past > fuel:
						DP[i][j] += 0
					else:
						DP[i][j] += DP[past][k]
		return sum((row[finish] for row in DP)) % (10 ** 9 + 7)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		(n, mod) = (len(locations), 1000000007)
		dp = [[0] * n for _ in range(fuel + 1)]
		for f in range(fuel + 1):
			for i in range(n):
				for j in range(n):
					if j != i and f >= abs(locations[i] - locations[j]):
						dp[f][i] += dp[f - abs(locations[i] - locations[j])][j]
			dp[f][finish] += 1
		return dp[fuel][start] % mod


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		locs = locations
		dp = [[0] * (fuel + 1) for _ in range(len(locs))]
		dp[start] = [1] * (fuel + 1)
		res = 0
		for f in range(1, fuel + 1):
			for i in range(len(locs)):
				for j in range(len(locs)):
					if i != j:
						d = abs(locs[i] - locs[j])
						if f - d >= 0:
							dp[i][f] = (dp[i][f] + dp[j][f - d]) % 1000000007
		res = dp[finish][fuel] % 1000000007
		return res


from functools import lru_cache

class Solution:

	def countRoutes(self, locations, start: int, finish: int, fuel: int) -> int:

		@lru_cache(None)
		def dfs(s, f):
			if f < 0:
				return 0
			res = 0
			if s == finish:
				res += 1
			for e in range(length):
				if s != e:
					res += dfs(e, f - matrix[s][e])
			return res % M
		M = 10 ** 9 + 7
		length = len(locations)
		matrix = [[0] * length for _ in range(length)]
		for i in range(length):
			for j in range(length):
				matrix[i][j] = matrix[j][i] = abs(locations[i] - locations[j])
		return dfs(start, fuel) % M


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		n = len(locations)
		mod = 10 ** 9 + 7

		@functools.lru_cache(None)
		def dfs(src, tar):
			if src == finish:
				if tar == 0:
					return 1
			res = 1 if src == finish else 0
			for i in range(n):
				if i != src:
					diff = abs(locations[i] - locations[src])
					if tar >= diff:
						res += dfs(i, tar - diff)
			return res
		return dfs(start, fuel) % mod


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		MOD = 10 ** 9 + 7

		@lru_cache(None)
		def dfs(i, f):
			ans = 0
			if i == finish:
				ans += 1
			for (j, nex) in enumerate(locations):
				if i != j and (used := abs(nex - locations[i])) <= f:
					ans += dfs(j, f - used)
			return ans % MOD
		return dfs(start, fuel)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		mod = 10 ** 9 + 7
		n = len(locations)

		@lru_cache(None)
		def dfs(start, fuel):
			cnt = 0
			if start == finish:
				cnt += 1
			for i in range(n):
				if i == start:
					continue
				cost = abs(locations[i] - locations[start])
				if cost <= fuel:
					cnt += dfs(i, fuel - cost)
			return cnt % mod
		return dfs(start, fuel)


class Solution:

	def countRoutes(self, L: List[int], S: int, F: int, FU: int) -> int:

		@lru_cache(None)
		def dp(i, cur_fuel):
			if cur_fuel == 0:
				return i == F
			total = 0
			if i == F:
				total += 1
			for k in range(len(L)):
				if k == i:
					continue
				consumption = abs(L[k] - L[i])
				if consumption <= cur_fuel:
					total += dp(k, cur_fuel - consumption)
			return total
		MOD = 10 ** 9 + 7
		return dp(S, FU) % MOD


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		(now, target) = (locations[start], locations[finish])

		@functools.lru_cache(None)
		def helper(now, fuel):
			if abs(now - target) > fuel:
				return 0
			ret = 1 if now == target else 0
			for l in locations:
				if l == now:
					continue
				cost = abs(l - now)
				if fuel >= cost:
					ret += helper(l, fuel - cost)
			return ret
		return helper(now, fuel) % (10 ** 9 + 7)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		MOD = 10 ** 9 + 7
		n = len(locations)

		@functools.lru_cache(None)
		def recur(curr, rest):
			res = 1 if curr == finish else 0
			for i in range(n):
				cost = abs(locations[curr] - locations[i])
				if curr != i and cost <= rest:
					res += recur(i, rest - cost)
			return res
		return recur(start, fuel) % MOD


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		mod = pow(10, 9) + 7

		@lru_cache(None)
		def dp(now, fuel):
			if fuel < 0:
				return 0
			res = 1 if now == finish else 0
			for nxt in range(len(locations)):
				if nxt != now:
					dis1 = abs(locations[nxt] - locations[now])
					if dis1 <= fuel:
						res += dp(nxt, fuel - dis1)
			return res % mod
		return dp(start, fuel) % mod


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		n = len(locations)
		dp = [[0] * n for i in range(fuel + 1)]
		dp[0][start] = 1
		for f in range(fuel):
			for x in range(n):
				if dp[f][x] == 0:
					continue
				for y in range(n):
					if x == y:
						continue
					g = f + abs(locations[x] - locations[y])
					if g <= fuel:
						dp[g][y] += dp[f][x]
		return sum((dp[i][finish] for i in range(fuel + 1))) % 1000000007


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		MOD = 10 ** 9 + 7
		n = len(locations)
		DP = [[-1] * (fuel + 1) for i in range(n)]
		DP[finish][0] = 1
		pos_finish = locations[finish]

		def search(loc, fuel):
			if DP[loc][fuel] != -1:
				return DP[loc][fuel]
			DP[loc][fuel] = 0
			pos = locations[loc]
			toEnd = abs(pos - pos_finish)
			if toEnd > fuel:
				return 0
			for loc2 in range(n):
				if loc2 == loc:
					continue
				tmp = abs(pos - locations[loc2])
				if tmp <= fuel:
					DP[loc][fuel] += search(loc2, fuel - tmp)
			DP[loc][fuel] += loc == finish
			DP[loc][fuel] %= MOD
			return DP[loc][fuel]
		search(start, fuel)
		return search(start, fuel)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		m = 10 ** 9 + 7

		@lru_cache(None)
		def dfs(s, e, f):
			if f < 0:
				return 0
			res = 1 if s == e else 0
			for l in locations:
				if l != s:
					res += dfs(l, e, f - abs(l - s))
			return res % m
		return dfs(locations[start], locations[finish], fuel)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:

		@lru_cache(None)
		def dfs(i: int, f: int) -> int:
			ans = 1 if i == finish else 0
			for j in range(len(locations)):
				diff = abs(locations[j] - locations[i])
				if j == i:
					continue
				elif diff <= f:
					ans += dfs(j, f - diff)
			return ans
		return dfs(start, fuel) % (10 ** 9 + 7)


from functools import lru_cache

class Solution:

	def countRoutes(self, locations, start, finish, fuel):
		MOD = 10 ** 9 + 7

		@lru_cache(None)
		def dp(u, f):
			ans = +(u == finish)
			du = locations[u]
			for (v, dv) in enumerate(locations):
				if v != u:
					delta = abs(du - dv)
					if delta <= f:
						ans += dp(v, f - delta)
						ans %= MOD
			return ans
		return dp(start, fuel)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		d = defaultdict(lambda : defaultdict(int))
		from functools import lru_cache

		@lru_cache(None)
		def dfs(i, fuel):
			if fuel < 0:
				return 0
			if (i, fuel) in d:
				return d[i][fuel]
			else:
				if i == finish:
					res = 1
				else:
					res = 0
				for j in range(len(locations)):
					expected = fuel - abs(locations[i] - locations[j])
					if i != j and expected >= 0:
						res += dfs(j, expected)
				d[i][fuel] = res
				return res
		return dfs(start, fuel) % (10 ** 9 + 7)


import functools

class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		graph = dict()
		for i in range(len(locations)):
			if i not in graph:
				graph[i] = dict()
			for j in range(len(locations)):
				if i != j:
					graph[i][j] = abs(locations[i] - locations[j])

		@functools.lru_cache(None)
		def bfs(position: int, fuel: int, count: int) -> int:
			if position == finish:
				res = count
			else:
				res = 0
			for neighbor in graph[position]:
				if fuel >= graph[position][neighbor]:
					res += bfs(neighbor, fuel - graph[position][neighbor], count)
			return res
		return bfs(start, fuel, 1) % (10 ** 9 + 7)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		MOD = 1000000007
		from functools import lru_cache

		@lru_cache(None)
		def backtrack(index, remaining_gas):
			if index == finish and remaining_gas == 0:
				return 1
			if remaining_gas == 0 and index != finish:
				return 0
			count = 0
			if index == finish:
				count = 1
			for i in range(len(locations)):
				if i == index:
					continue
				dist = abs(locations[i] - locations[index])
				if dist <= remaining_gas:
					count = (count + backtrack(i, remaining_gas - dist)) % MOD
			return count
		return backtrack(start, fuel)


class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		MOD = 1000000007

		@functools.lru_cache(maxsize=None)
		def calc(start, fuel):
			ret = 0
			if start == finish:
				ret += 1
			for i in range(len(locations)):
				if i == start:
					continue
				d = abs(locations[i] - locations[start])
				if d > fuel:
					continue
				ret = (ret + calc(i, fuel - d)) % MOD
			return ret
		return calc(start, fuel)


from functools import lru_cache

class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		start = locations[start]
		finish = locations[finish]

		@lru_cache(None)
		def helper(start, fuel):
			if fuel < 0:
				return 0
			summ = start == self.finish
			for i in locations:
				if i != start:
					remaining_fuel = fuel - abs(start - i)
					summ += helper(i, remaining_fuel)
			print((start, fuel, summ))
			return summ
		self.finish = finish
		return helper(start, fuel) % (10 ** 9 + 7)


MOD = 10 ** 9 + 7

class Solution:

	def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
		n = len(locations)

		@lru_cache(None)
		def dp(pos, left):
			ans = int(pos == finish)
			if left == 0:
				return ans
			for i in range(n):
				if i != pos:
					cost = abs(locations[pos] - locations[i])
					if cost <= left:
						ans += dp(i, left - cost)
						if ans > MOD:
							ans %= MOD
			return ans
		return dp(start, fuel)