星期天早晨到来了，整个秋天都显得明媚而凉爽，洋溢着生机。每个人心中都有一首歌，若是年轻的心，那歌声便从唇间流出。每张脸上都洋溢着喜色，每个步伐都带着欢呼。汤姆出现在人行道上，手里提着一桶石灰水和一把长柄刷。他打量着公园里的石头棋盘，顿时所有欢乐离他而去，一种深沉的忧郁笼罩了他的心灵。那是一个巨大的棋盘，长 n 英尺，宽 m 英尺。对他来说，生命似乎空洞无物，生存只是一种负担。

他叹了口气，用刷子蘸了点石灰水，琢磨着如何开始。他知道自己需要选择一个起点，这可以是棋盘上的任意一个格子。他将这个格子粉刷成白色，然后移动到相邻的一个格子；重复这个操作，直到整个棋盘都被粉刷完毕，他可以在任意地方结束工作。即使他脱掉鞋子，他的脚印也会弄脏已经粉刷过的区域。因此，避免回到已经完成的格子将是一个明智的选择。

可是汤姆的精力很快就耗尽了。他开始想起自己原计划今天要玩的乐趣，悲伤便成倍增长。很快，那些无拘无束的男孩和女孩们就会沿着南京航空航天大学江宁校区的砚湖边轻快走来，他们将有机会参加 ICPC 竞赛，面对有趣的算法问题。他盯着棋盘，一种突如其来的好奇心促使他关注起任意两个已粉刷格子之间仅经过已粉刷格子的最短路径，其中相邻格子应共享一条公共边。

“见鬼！最短距离可能会变化。我得阻止这种事情发生。”

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

而下面这种策略则不予考虑：

现在他想知道，共有多少种不同的令人满意的策略能够将整个棋盘粉刷完毕。你能帮帮他吗？

第一行包含一个整数 T~(1\le T\le 10^5)，表示测试数据的组数。

对于每组测试数据，一行包含两个整数 n 和 m~(1\le n, m\le 10^6)，描述棋盘的尺寸。

对于每组测试数据，输出不同的令人满意的策略数目对 (10^9+7) 取模的结果。

ICPC 2019 Nanjing R