### 问题描述 小 $L$ 有 $n$ 个红宝石和 $m$ 个蓝宝石。红宝石和蓝宝石都是可区分的。现在小 $L$ 想把这些宝石排成一列，使得：对于任意两个相邻的宝石，它们都不同色。请问有多少种填法？答案对 $1e9+7$ 取模。 ### 输入格式 第一行一个正整数 $T$，表示测试点的个数。 接下来 $n$ 行，每行有一个长度为 $m$ 的字符串，表示整个矩阵。 接下来 $T$ 行，每行有两个数 $n,m$，表示红宝石和蓝宝石的个数。 ### 输出格式 输出共 $T$ 行，每一行表示一个询问的答案。 ### 样例输入 ``` 2 2 2 3 2 ``` ### 样例输出 ``` 8 12 ``` ### 说明 考虑 $2$ 个红宝石和 $2$ 个蓝宝石的情况，将红宝石编号为 $A,B$，蓝宝石编号为 $C,D$，那么合法的排列有：$ACBD, BCAD, ADBC, BDAC, CADB, CBDA, DACB, DBCA$ ,共 $8$ 种，类似地，也可以推出 $3$ 个红宝石 $2$ 个蓝宝石的情况有 $12$ 种。 ### 评测数据范围 对于 $30\\%$ 的数据，满足 $n,m \leq 5,T \leq 5$。 对于 $60\\%$ 的数据，满足 $n,m \leq 1000,T \leq 1000$。 对于 $100\\%$ 的数据，满足 $1 \leq n,m \leq 100000,1 \leq T \leq 100000$。