The universe is a 2D array of dimensions $N * M$. You are standing in cell $(1, 1)$ at the start.
You can make a move in three different directions:

• ↓
• →
• ↘

The biggest length of a move the man can make is $K$. If the current position of the man is $(x, y)$, in a one-step he can go to:

• $(x+w, y)$ where $w ≤ K$ and $x+w ≤ N$.
• $(x, y+w)$ where $w ≤ K$ and $y+w ≤ M$.
• $(x+w, y+w)$ where $w ≤ K$ and $x+w ≤ N$ and $y+w ≤ M$.

In how many ways can you reach the cell $(N, M)$?

Since the solution can be very large, compute it modulo $10^9 + 7$.

Input format

• The first line contains $Q$ denoting the number of test cases.
• Each of the next $Q$ lines contains three integers, $N$, $M$ and $K$.

Output format

For each test case, output on a new line the count of ways to reach the cell $(N,M)$ modulo $10^9 + 7$.

Constraints

$1 \leq Q, N, M, K \leq 1000$
The sum of $N * M$ over all test cases won't exceed $10^8$.