장난감

심사위원장은 원판 두 개로 장난감을 하나 만든다. 하나는 빨간 원판, 하나는 파란 원판이고, 두 원판의 중심을 축 하나가 관통한다. 두 원판은 이 축을 중심으로 각각 따로 돈다.

빨간 원판의 가장자리에는 집게가 $n$개, 파란 원판의 가장자리에는 집게가 $m$개 같은 간격으로 달려 있다. 빨간 원판의 집게와 파란 원판의 집게는 잘 휘는 끈으로 이을 수 있다. 집게 하나에 끈을 여러 개 맬 수 있지만, 집게 두 개 사이를 잇는 끈은 많아야 하나다.

$n$과 $m$이 주어졌을 때 심사위원장이 만들 수 있는 서로 다른 장난감의 개수를 1,000,000,007로 나눈 나머지를 구하라. 두 원판을 축 둘레로 돌려서 한 장난감을 다른 장난감과 똑같이 만들 수 있으면 둘은 같은 장난감이다. 이때 두 원판을 돌리는 각도는 서로 달라도 된다. 끈이 어느 집게 두 개를 잇는지만 중요하고, 끈이 두 원판 사이 공간에서 어떤 경로를 그리는지는 상관없다.

아래 그림에서 (a)와 (b)는 같은 장난감이다. 왼쪽 빨간 원판을 반시계 방향으로 한 칸, 오른쪽 파란 원판을 반시계 방향으로 네 칸 돌리면 (a)가 (b)가 된다. (c)는 다른 장난감이다.

첫째 줄에 데이터 집합의 개수 $P$가 주어진다 ($1 \le P \le 1000$).

다음 $P$개 줄에 데이터 집합이 한 줄에 하나씩 주어진다. 각 줄에는 데이터 집합 번호 $K$와 정수 $n$, $m$이 공백으로 구분되어 주어진다 ($2 \le n, m \le 10^7$). 모든 데이터 집합은 서로 독립이고, 처리 방식은 같다.

각 데이터 집합마다 한 줄에 데이터 집합 번호 $K$, 공백 하나, 그 $n$과 $m$에 대한 서로 다른 장난감의 개수를 1,000,000,007로 나눈 나머지를 차례로 출력한다.