题目背景

Wolfycz很喜欢画画（雾

题目描述

Wolfycz喜欢网格图，他希望在网格图上画上一些黑格子，使得每一列都恰好有一个黑格子。但是黑格子太乱了不好看，所以Wolfycz希望黑格子按列号依次连线是下降的，具体来讲，每列黑格子所在行号不得小于前一列黑格子所在行号（我们令左上角为第一行第一列）

Wolfycz觉得这样画出来的图非常漂亮，但是Wolfycz有时候觉得连线要严格下降才好看（即每列黑格子所在行号必须大于前一列黑格子所在行号），有时候觉得连线只要不上升就好看（即每列黑格子所在行号不得小于前一列黑格子所在行号）。现在Wolfycz想知道，对于一个$N×M$的网格图，他能画出多少个好看的图？两个图不相同，当且仅当存在某一列的黑格子，它在两个图中对应的行号不同

UPD：$N$行$M$列

输入格式

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

接下来每一行读入三个整数$N,M,opt$，表示$N×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\leqslant 5,N\leqslant 8,M\leqslant 8$

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

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

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