You are given two integers n and m which represent the size of a 1-indexed grid. You are also given an integer k, a 1-indexed integer array source and a 1-indexed integer array dest, where source and dest are in the form [x, y] representing a cell on the given grid.
You can move through the grid in the following way:
[x1, y1] to cell [x2, y2] if either x1 == x2 or y1 == y2.x1 == x2 and y1 == y2.Return the number of ways you can reach dest from source by moving through the grid exactly k times.
Since the answer may be very large, return it modulo 109 + 7.
Example 1:
Input: n = 3, m = 2, k = 2, source = [1,1], dest = [2,2] Output: 2 Explanation: There are 2 possible sequences of reaching [2,2] from [1,1]: - [1,1] -> [1,2] -> [2,2] - [1,1] -> [2,1] -> [2,2]
Example 2:
Input: n = 3, m = 4, k = 3, source = [1,2], dest = [2,3] Output: 9 Explanation: There are 9 possible sequences of reaching [2,3] from [1,2]: - [1,2] -> [1,1] -> [1,3] -> [2,3] - [1,2] -> [1,1] -> [2,1] -> [2,3] - [1,2] -> [1,3] -> [3,3] -> [2,3] - [1,2] -> [1,4] -> [1,3] -> [2,3] - [1,2] -> [1,4] -> [2,4] -> [2,3] - [1,2] -> [2,2] -> [2,1] -> [2,3] - [1,2] -> [2,2] -> [2,4] -> [2,3] - [1,2] -> [3,2] -> [2,2] -> [2,3] - [1,2] -> [3,2] -> [3,3] -> [2,3]
Constraints:
2 <= n, m <= 1091 <= k <= 105source.length == dest.length == 21 <= source[1], dest[1] <= n1 <= source[2], dest[2] <= mLoading editor...
3 2 2 [1,1] [2,2]