painting
题目背景
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$取模
输入输出样例
输入样例 #1
5
5 2 1
5 3 0
3 4 0
8 4 1
6 2 1
输出样例 #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$