Just no more counters

Time Limit: 1 Second    Memory Limit: 65536 KB

Once upon a time there was a teacher. He was always telling his students: “You can solve any problem using just counters.” The teacher meant that it is better to find a solution using counters even if there are other solutions!

By the way, you are now asked to count the number of parallelograms in a grid of R rows and C columns (as shown in the figure). Vertices of parallelogram should be on the grid points and at least two edges of parallelogram should be parallel to the axis (i.e. vertical or horizontal). 


As you might already know, the ‘execution time’ is very important in a programming contest so it seems that you cannot use a counter here! Feel free to calculate the answer in any way you want but make it fast enough. As this number can be very large you should calculate it modulo 1,000,000,007. 

 

Input

The first line begin with an integer T (T ≤ 10000), the number of tests. Each test will be in a separate line contain two integers R and C (1 ≤ R, C ≤ 106), dimensions of the grid. 

 

Output

For each test print the number of parallelograms in a single line.

 

Sample Input

3
1 1
2 3
123 456

Sample Output

1
54
450228282
Submit

Source: AUT 2012