All Tracks Math Combinatorics Basics of Combinatorics Problem

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...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

August Circuits '17

OTHER PROBLEMS OF THIS CHALLENGE
Уведомления
View All Notifications

?