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$