Stuck in an Infinite Grid
Tag(s):

## Combinatorics basics, Easy-Medium, Mathematics

Problem
Editorial
Analytics

Consider a 2-dimensional Infinite Grid. Find the number of K length walks from the point $S(x_s, y_s)$ to the point $T(x_t, y_t)$. Here S and T may be the same point.

You are allowed to move in the four cardinal directions only, i.e. from a point $(x, y)$ you can move to $(x + 1, y)$, $(x, y + 1)$, $(x - 1, y)$ and $(x, y - 1)$. Two points P and Q are adjacent if you can move from one to the other.

Moreover, you can visit the same coordinate multiple times.

A walk of length K can be denoted as a sequence of $K + 1$ coordinates $P_i$ for $0 \le i \le K$, where $P_i$ and $P_{i+1}$ are adjacent, for all $0 \le i \lt K$

Two walks of length K, having coordinate sequences as $P_i$ and $Q_i$ are considered different if there exists an integer j such that $0 \le j \le K$ and $P_j \neq Q_j$.

Input Format

The first line will contain the integer T, denoting the number of test cases.

Each of the next T lines will contain 5 space-separated integers denoting the value of $x_s, y_s, x_t, y_t, K$ respectively.

Output Format

For each test case, print the number of K length walks from $S(x_s, y_s)$ to $T(x_t, y_t)$ modulo $10^9 + 7$

Constraints

$1 \le T \le 20$

$0 \le x_s, y_s, x_t, y_t \le 2*10^5$

$1 \le K \le 2*10^5$

SAMPLE INPUT
2
0 0 0 1 3
0 0 1 2 3

SAMPLE OUTPUT
9
3

Explanation

For the first test case, two of the total 9 possible ways are:

$(0, 0) \to (0, 1) \to (0, 0) \to (0, 1)$

$(0, 0) \to (0, -1) \to (0, 0) \to (0, 1)$

Time Limit: 2,0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

August Circuits '17

OTHER PROBLEMS OF THIS CHALLENGE
• Basic Programming > Implementation
• Algorithms > Graphs
• Algorithms > Dynamic Programming