409239: GYM103466 B Chessboard

Sunday morning has come, and all the autumn would be bright and cool, and brimming with life. There was a song in every heart, and if the heart was young the music issued at the lips. There was cheer in every face and a whoop in every step. Tom appeared on the sidewalk with a bucket of whitewash and a long-handled brush. He surveyed the stone chessboard in the park, and all gladness left him and a deep melancholy settled down upon his spirit. A giant chessboard, that is $$$n$$$ feet long and $$$m$$$ feet wide. Life to him seemed hollow, and existence but a burden.

Sighing, he dipped his brush with a little whitewash and thought how to start. He knew that he would select a starting point, which should be an arbitrary block in the chessboard. He would whitewash the block and move to an adjacent one; repeat the operation and finish his work in any place when the whole chessboard has been whitewashed. His footprints would defile a painted region even if he took off his shoes. So avoiding to go back to a completed block would be a wise choice.

But Tom's energy did not last. He began to think of the fun he had planned for this day, and his sorrows multiplied. Soon the free boys and girls would come tripping along the Yan Lake inside Nanjing University of Aeronautics and Astronautics Jiangning campus, and they would have the chance to take part in the ICPC contest facing interesting algorithms problems. Staring at the chessboard, a sudden curiosity urged him to pay attention to, between any two painted blocks, the shortest paths only passing painted blocks in which adjacent blocks should share a common edge.

"Damn it! The shortest distances may vary. I have to stop such a thing happening."

He quickly imagined a strategy that the shortest distance between any two blocks would remain unchanged after they were painted, and it would be a satisfactory beginning:

and another strategy not to be considered:

Now he wants to know how many different satisfactory strategies are there that can whitewash the whole chessboard. Can you help him?

The first line contains an integer $$$T~(1\le T\le 10^5)$$$ indicating the number of test cases.

For each test case, a single line containing two integers $$$n$$$ and $$$m~(1\le n, m\le 10^6)$$$ describes the size of the chessboard.

For each test case, output the number of different satisfactory strategies modulo $$$(10^9+7)$$$.

4
1 3
3 2
3 3
4 4

2
12
24
80