Toys

The head judge builds one toy out of two discs, a red one and a blue one. An axis runs through the centers of both discs, and each disc turns around that axis on its own.

The red disc has $n$ clamps spaced evenly around its edge, and the blue disc has $m$. A clamp on the red disc can be joined to a clamp on the blue disc by a flexible string. A clamp can carry several strings, but two clamps are joined by at most one string.

For given $n$ and $m$, count the different toys the head judge can build, modulo 1,000,000,007. Two toys are the same when turning the discs around the axis makes one of them look exactly like the other, and the two turning angles do not have to be equal. Only the pair of clamps that a string joins matters, not the path the string takes through the space between the discs.

In the figure below, (a) and (b) are the same toy. Turn the red disc on the left one step counterclockwise and the blue disc on the right four steps counterclockwise, and (a) becomes (b). (c) is a different toy.

The first line contains the number of data sets $P$ ($1 \le P \le 1000$).

Each of the next $P$ lines holds one data set: the data set number $K$, then the integers $n$ and $m$, separated by spaces ($2 \le n, m \le 10^7$). The data sets are independent of each other and are processed the same way.

For each data set print one line: the data set number $K$, a single space, then the number of different toys for that $n$ and $m$, modulo 1,000,000,007.