P5135 painting

Wolfycz很喜欢画画（雾

Wolfycz喜欢网格图，他希望在网格图上画上一些黑格子，使得每一列都恰好有一个黑格子。但是黑格子太乱了不好看，所以Wolfycz希望黑格子按列号依次连线是下降的，具体来讲，每列黑格子所在行号不得小于前一列黑格子所在行号（我们令左上角为第一行第一列） Wolfycz觉得这样画出来的图非常漂亮，但是Wolfycz有时候觉得连线要严格下降才好看（即每列黑格子所在行号必须大于前一列黑格子所在行号），有时候觉得连线只要不上升就好看（即每列黑格子所在行号不得小于前一列黑格子所在行号）。现在Wolfycz想知道，对于一个$N×M$的网格图，他能画出多少个好看的图？两个图不相同，当且仅当存在某一列的黑格子，它在两个图中对应的行号不同 UPD：$N$行$M$列

无

无

对于$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$