说明

Wolfycz 喜欢网格图，他希望在网格图上画上一些黑格子，使得每一列都恰好有一个黑格子。

但是黑格子太乱了不好看，所以 Wolfycz 希望黑格子按列号依次连线是下降的，具体来讲，每列黑格子所在行号不得小于前一列黑格子所在行号（我们令左上角为第一行第一列）

Wolfycz 觉得这样画出来的图非常漂亮，但是 Wolfycz 有时候觉得连线要严格下降才好看（即每列黑格子所在行号必须大于前一列黑格子所在行号），有时候觉得连线只要不上升就好看（即每列黑格子所在行号不得小于前一列黑格子所在行号）。

现在 Wolfycz 想知道，对于一个 $N\times M$ 的网格图，他能画出多少个好看的图？两个图不相同，当且仅当存在某一列的黑格子，它在两个图中对应的行号不同。

UPD：$N$ 行 $M$ 列。

输入格式

第一行读入 $T$，表示有 $T$ 组数据。

接下来每一行读入三个整数 $N,M,opt$，表示 $N\times M$ 的矩阵，如果 $opt$ 为 $1$，则 Wolfycz 认为连线要严格下降才好看；如果 $opt$ 为 $0$，则 Wolfycz 认为连线只要不上升就好看。

输出格式

输出共 $T$ 行，每行一个整数，表示 Wolfycz 能画出不同的图的个数，答案对 $10^9+7$ 取模。

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

10
35
15
70
15

提示

对于 $20\%$ 的数据，$T\leq 5,N\leq 8,M\leq 8$。

对于另外 $20\%$ 的数据，$N=1$ 或 $M=1$。

对于另外 $20\%$ 的数据，$N\leq 10^6,M\leq 10^6$。

对于 $100\%$ 的数据，$T\leq 50,N\leq 10^{18},M\leq 10^6$。