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 450228282Submit
Source: AUT 2012