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