You are given two integers n and m representing the dimensions of a $1$ indexed $n imes m$ grid. You are also given an integer k and two arrays source and dest, each of length $2$, where source is the starting cell and dest is the destination cell.

At each step, you can move from the current cell to any other cell that is located in the same row or the same column as the current cell.

Return the total number of distinct paths to reach dest from source in exactly k steps. Since the answer may be large, return it modulo $10^9 + 7$.

Constraints:

• $2 \leq$ n, m $\leq 10^9$

• $1 \leq$ k $\leq 10^5$

• source.length $==$ dest.length $== 2$

• $1 \leq$ source[0], dest[0] $\leq$ n

• $1 \leq$ source[1], dest[1] $\leq$ m

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

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

Implement your solution in the following coding playground.