I I U P C 2 0 0 9
Problem G: Gridland Airports
The country ‘Gridland’ is a strange country which have R*C cities arranged in R rows and C columns. The bottom-left city is (1,1) and the upper-right city is (R,C). The governor of ‘Gridland’ has hired you to assign some flight routes between the cities in ‘Gridland’. You have to establish minimum number of direct flight connections such that every pair of city is connected by a direct flight or some flight sequences. If a flight connection is established between two cities that can be used in both directions. But there is a restriction: a direct flight connection between two cities A(r1, c1) and B(r2, c2) can be established only if |r1-r2|+|c1-c2| == odd. Find how many ways you can setup flight routes such that every pair of city is connected and the number of direct flight connections is minimum.
Input
First line of input is T(≤5000) which is the number of cases. Then there are T lines each containing two numbers R, C and 2 ≤ R, C ≤ 10^8.
Output
Output the number of ways to setup the flight route network. As the answer could be very big so output answer MOD (10^16+7).
Sample Input	Output for Sample Input
2 2 2 49 49	4 1661809100947531
Problem Setter: Tasnim Imran Sunny Special Thanks: Md. Mahbubul Hasan, Md. Arifuzzaman Arif