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