下面给出的是英语词典中排列为矩阵的单词
MATHE
ATHEM
THEMA
HEMAT
EMATI
MATIC
ATICS
跟踪矩阵从左上角开始,每步向右或向下移动,到达矩阵的右下角.确保任何此类跟踪都生成相同的单词.对于长度为m + n-1的给定单词写成大小为m*n的矩阵,可以有多少这样的跟踪？
输入格式第一行输入包含一个整数T.每行都有T个测试用例.每行包含2个空格分隔的整数m和n,表示写入的矩阵有m行,每行有n个字符.
约束:
1 <= T <= 103
1 ? m,n ? 106
输出格式打印可以跟踪单词的方式(S)的数量,如问题陈述中所述.如果数字大于10,则为9 +7,请打印S mod(10 rest to power 9 +7)
样本输入
1
2 3
样本输出
3
解释让我们考虑写为矩阵的单词AWAY
AWA
WAY
在这里,矩阵中的单词AWAY可以用3种不同的方式跟踪,遍历RIGHT或DOWN.
AWA
Y
AW
AY
A
WAY