In the far, far distant future, a war unleashes between humans and the AI, which results in the total destruction of the universe. In the end of all the catastrophe, you find yourself in a rather small world, a $3\times3$ grid, and life has become quite boring.

In an attempt to humor yourself, you start solving unique math questions, and here's one you have been trying to solve:

• You are currently standing on the cell $S$ of the grid.
• In a single step you can move to any of the adjacent grid cells (here adjacent cells also includes diagonally adjacent cells) with uniformly equal probability.
• For example, if you are currently on cell $1$ you may move to any one of the cells $\{2, 4, 5\}$ with probability ${1 \over 3}$. Similarly, say you are standing on cell $5$ you may move to any one of the cells $\{1, 2, 3, 4, 6, 7, 8, 9\}$ with probability ${1 \over 8}$.
• In a step, you cannot move outside the grid, and you also cannot remain in the same cell.
• You want to find if you take $K$ steps, starting from cell $S$ then what is the probability that you would be standing on cell $T$.
• If the probability is ${P \over Q}$, you have to find the value of $P * {Q^{-1}}$ modulo $10^9 + 7$.

$Inputs:$

First line of input will contain the number of test cases $N$.

Each of next $N$ lines will contain $S, T$ and $K$ for that case.

$Outputs:$

Output $N$ lines containing the probability for each testcase as described before.

$Constraints:$

$1 \le N \le 100$

$1 \le S, T \le 9$

$1 \le K \le 10^{18}$

Problem Setter: Kevin Mathew T