# 2912. Number of Ways to Reach Destination in the Grid

## Description

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:

• You can go from cell [x1, y1] to cell [x2, y2] if either x1 == x2 or y1 == y2.
• Note that you can't move to the cell you are already in e.g. 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 <= 109
• 1 <= k <= 105
• source.length == dest.length == 2
• 1 <= source, dest <= n
• 1 <= source, dest <= m

## Solutions

• class Solution {
public int numberOfWays(int n, int m, int k, int[] source, int[] dest) {
final int mod = 1000000007;
long[] f = new long;
f = 1;
while (k-- > 0) {
long[] g = new long;
g = ((n - 1) * f + (m - 1) * f) % mod;
g = (f + (n - 2) * f + (m - 1) * f) % mod;
g = (f + (m - 2) * f + (n - 1) * f) % mod;
g = (f + f + (n - 2) * f + (m - 2) * f) % mod;
f = g;
}
if (source == dest) {
return source == dest ? (int) f : (int) f;
}
return source == dest ? (int) f : (int) f;
}
}

• class Solution {
public:
int numberOfWays(int n, int m, int k, vector<int>& source, vector<int>& dest) {
const int mod = 1e9 + 7;
vector<long long> f(4);
f = 1;
while (k--) {
vector<long long> g(4);
g = ((n - 1) * f + (m - 1) * f) % mod;
g = (f + (n - 2) * f + (m - 1) * f) % mod;
g = (f + (m - 2) * f + (n - 1) * f) % mod;
g = (f + f + (n - 2) * f + (m - 2) * f) % mod;
f = move(g);
}
if (source == dest) {
return source == dest ? f : f;
}
return source == dest ? f : f;
}
};

• class Solution:
def numberOfWays(
self, n: int, m: int, k: int, source: List[int], dest: List[int]
) -> int:
mod = 10**9 + 7
f = [1, 0, 0, 0]
for _ in range(k):
g =  * 4
g = ((n - 1) * f + (m - 1) * f) % mod
g = (f + (n - 2) * f + (m - 1) * f) % mod
g = (f + (m - 2) * f + (n - 1) * f) % mod
g = (f + f + (n - 2) * f + (m - 2) * f) % mod
f = g
if source == dest:
return f if source == dest else f
return f if source == dest else f


• func numberOfWays(n int, m int, k int, source []int, dest []int) int {
const mod int = 1e9 + 7
f := []int{1, 0, 0, 0}
for i := 0; i < k; i++ {
g := make([]int, 4)
g = ((n-1)*f + (m-1)*f) % mod
g = (f + (n-2)*f + (m-1)*f) % mod
g = (f + (m-2)*f + (n-1)*f) % mod
g = (f + f + (n-2)*f + (m-2)*f) % mod
f = g
}

if source == dest {
if source == dest {
return f
}
return f
}

if source == dest {
return f
}
return f
}