D. Count The Raviolis { }
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Aziz is making raviolis today! He has rolled out a large sheet of dough that can be represented as an $$$n \times m$$$ grid of unit squares.

A ravioli is defined as any rectangular section of the dough with integer side lengths whose sides are parallel to the edges of the main grid.

Aziz's dough is magical: every time he chooses a valid rectangular area to cut, he simply notes its dimensions and position, and the dough remains intact for his next calculation.

Help Aziz find the total number of distinct ravioli (sub-rectangles) he can identify within the $$$n \times m$$$ grid.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ $$$( 1 \le t \le 10^5)$$$. The description of the test cases follows.

Each test case contains two integers $$$n,m$$$ $$$(1 \le n,m \le 10^{5})$$$– the size of the grid

Output

For each test case:

Output an integer answer modulo $$$10^9+7$$$.

Example
Input
5
1 1
2 2
2 3
3 3
50 34
Output
1
9
18
36
758625
Note

$$$n \times m$$$ ravioli roll

an image showcasing the number of cuts of the $$$2 \times 2 $$$ roll

The ways to cut the $$$2 \times 2$$$ roll:

  • four $$$ 1 \times 1$$$ raviolis
  • two $$$ 2 \times 1$$$ raviolis
  • two $$$ 1 \times 2$$$ raviolis
  • one $$$ 4 \times 4$$$ raviolis