Alfred: “You gonna go to war ?? “
Bruce : “ He is the one who brought the WAR TO US . We believe that even if there is 1 percent chance that he is our enemy then we have to take it as an absolute certainty. He has the power to wipe out the entire
human race . I might have to destroy him . “

Bat of Gotham is all set to fight against the Son of Krypton .

Consider Gotham to be a matrix of $N \times M$ locations.

Batman intends to place an explosive at each of these locations ,
such that the power of explosives
ranges from 1 to $N \times M . No 2$ locations will have explosives of same power.
Alfred examined the condition of each of the $N \times M$ locations precisely , and made a crucial
observation .

Consider 2 distinct locations , denoted by (A1,B1) and (A2,B2) respectively – if (A1|B1) > (A2|B2) , then (A1,B1) location will hold higher power explosive than the explosive at (A2,B2) , and vice-versa.
| is BITWISE OR .

Since our Batman doesn’t want to leave any chance of destroying Superman , he needs to know all
possible methods of placing explosives .

INPUT CONSTRAINTS:-
T ≤ 5
1 ≤ N,M ≤ 3500
INPUT:-
You are provided with T- the number of test cases
Each test case has 2 integers N and M .
OUTPUT:-
Output the total number of ways to place explosives in N x M locations . Since, this answer can be large, output it modulo 10^9+7

Problem setter : Shivam Garg

SAMPLE INPUT
1
1 2

SAMPLE OUTPUT
1

Explanation

The 1 way of arranging explosives is:-
1 2
(because the other arrangement – 2 1 violates the given condition ).

见题面

见题面