Background

Wolfycz really likes painting (sort of).

Problem Description

Wolfycz likes grid diagrams. He wants to paint some black cells on a grid so that each column has exactly one black cell. However, black cells look messy, so Wolfycz wants the polyline formed by connecting the black cells from left to right (in increasing column order) to be descending. More specifically, the row index of the black cell in each column must be no smaller than the row index of the black cell in the previous column (we define the top-left corner as row $1$, column $1$).

Wolfycz thinks such diagrams look very nice, but sometimes he feels that the polyline must be strictly descending to look good (i.e., the row index of the black cell in each column must be greater than that in the previous column). Sometimes he feels it is enough that the polyline does not go up (i.e., the row index of the black cell in each column must be no smaller than that in the previous column). Now Wolfycz wants to know: for an $N \times M$ grid, how many nice diagrams can he draw? Two diagrams are different if and only if there exists a column whose black cell is in different rows in the two diagrams.

UPD: $N$ rows and $M$ columns.

Input Format

The first line contains $T$, meaning there are $T$ test cases.

Each of the next $T$ lines contains three integers $N, M, opt$, describing an $N \times M$ matrix. If $opt$ is $1$, then Wolfycz thinks the polyline must be strictly descending to look good. If $opt$ is $0$, then Wolfycz thinks it is enough that the polyline does not go up.

Output Format

Output $T$ lines in total. Each line contains one integer, the number of different diagrams Wolfycz can draw, modulo $10^9 + 7$.

5
5 2 1
5 3 0
3 4 0
8 4 1
6 2 1

10
35
15
70
15

Hint

For $20\%$ of the testdata, $T \leqslant 5, N \leqslant 8, M \leqslant 8$.

For another $20\%$ of the testdata, $N = 1$ or $M = 1$.

For another $20\%$ of the testdata, $N \leqslant 10^6, M \leqslant 10^6$.

For $100\%$ of the testdata, $T \leqslant 50, N \leqslant 10^{18}, M \leqslant 10^6$.

Translated by ChatGPT 5