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\)