周日早晨到了，秋高气爽，生机勃勃。每个人的心中都有一首歌，如果心还年轻，歌声就会从唇间流淌出来。每张脸上都洋溢着喜悦，每一步都充满了活力。汤姆出现在人行道上，手里拿着一桶粉刷用的白漆和一把长柄刷子。他打量着公园里的石制棋盘，所有的快乐都离他而去，一种深深的忧郁笼罩了他的心头。这是一个巨大的棋盘，长为 $n$ 英尺，宽为 $m$ 英尺。生活对他来说似乎空虚，存在不过是一种负担。

他叹了口气，用刷子蘸了一点白漆，思考着该如何开始。他知道他会选择一个起点，这应该是棋盘上的任意一个方格。他会粉刷这个方格，然后移动到相邻的一个方格；重复这个操作，并在整个棋盘都被粉刷完毕后的任何地方结束他的工作。他的足迹会弄脏已经粉刷过的区域，即使他脱掉鞋子也是如此。因此，避免回到已经完成的方格是一个明智的选择。

但汤姆的精力并没有持续太久。他开始想起他为这一天计划的乐趣，他的忧虑加倍了。很快，自由的男孩女孩们就会沿着南京航空航天大学江宁校区的砚湖蹦蹦跳跳地走来，他们将有机会参加 ICPC 竞赛，面对有趣的算法问题。盯着棋盘，一种突如其来的好奇心促使他关注：在任何两个已粉刷的方格之间，只经过已粉刷方格的最短路径，其中相邻的方格应该共享一条公共边。

“该死！最短距离可能会改变。我必须阻止这种事情发生。”

他很快构思出一种策略，使得任何两个方格之间的最短距离在它们被粉刷后保持不变，这是一个令人满意的开始：

以及另一种不予考虑的策略：

现在他想知道，有多少种不同的、能够粉刷整个棋盘的满意策略？你能帮帮他吗？

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10^5$)，表示测试用例的数量。

对于每个测试用例，一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 10^6$)，描述棋盘的大小。

输出格式

对于每个测试用例，输出不同满意策略的数量，对 $10^9 + 7$ 取模。

样例

样例输入 1

4
1 3
3 2
3 3
4 4

样例输出 1

2
12
24
80