题目描述

Lisa 正在给 Yukina 讲八皇后问题，八皇后问题指的是在 \(8 \times 8\) 的国际象棋棋盘中，放八个皇后使得所有皇后之间互不攻击有多少种方案。但 Yukina 完全学不会，因为她觉得国际象棋一点都不好玩，没有中国象棋中“炮”这种可以有趣的棋子（“炮”的攻击方式）。

Yukina 向 Lisa 提出了一个问题，如果有一个 \(n \times m\) 的中国象棋棋盘，最多可以放多少个“炮”？Lisa 思考了一会后就给出了这个问题的答案，Yukina 又继续追问：有多少种放“炮”的方案可以放最多的“炮”，使得任意两个“炮”之间不会互相攻击。

由于这个答案可能很大，因此你需要将方案数对 \(10^9 + 7\) 取模。

输入格式

第一行输入一个正整数 \(T(1 \le T \le 10^6)\)，表示数据组数。

对于每一组数据：

第一行输入两个正整数 \(n, m(1 \le n, m \le 5000)\)，表示棋盘大小。

输出格式

对于每组数据输出一个整数表示答案。

样例输入

3
2 2
2 3
6 8

样例输出

1
9
49432320