정사각형 세기

Mr. Panda는 최근 Square Off라는 새로운 게임에 푹 빠졌다. 이 게임에서 플레이어들은 점들이 균일한 간격으로 배치된 직사각형 격자에서 가능한 한 많은 서로 다른 정사각형을 찾기 위해 경쟁한다. 정사각형을 찾으려면 플레이어는 정사각형의 꼭짓점을 이루는 네 점을 식별해야 한다. 물론 정사각형의 각 변은 길이가 같아야 하지만, 그 길이가 얼마인지는 중요하지 않으며 정사각형이 반드시 격자의 축과 나란할 필요도 없다. 플레이어는 이 방식으로 찾은 서로 다른 정사각형마다 한 점을 얻는다. 두 정사각형을 구성하는 네 점의 집합이 서로 다를 때, 그리고 그럴 때에만 두 정사각형은 서로 다르다.

Mr. Panda에게 방금 점이 R행 C열로 배치된 격자가 주어졌다. 이 격자에서 서로 다른 정사각형을 몇 개 찾을 수 있는가? 그 수가 매우 클 수 있으므로, 답을 $10^{9}$ + 7 (1000000007)로 나눈 나머지를 출력한다.

제한

1 ≤ T ≤ 100. 시간 제한: 테스트 세트당 20초. 메모리 제한: 1GB.

작은 데이터 세트 (테스트 세트 1 - 공개)

2 ≤ R ≤ 1000. 2 ≤ C ≤ 1000.

큰 데이터 세트 (테스트 세트 2 - 비공개)

2 ≤ R ≤ $10^{9}$. 2 ≤ C ≤ $10^{9}$.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 줄이 주어진다. 각 줄에는 두 정수 R과 C가 주어지며, 각각 격자의 각 행과 열에 있는 점의 수를 나타낸다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x은 테스트 케이스 번호이며 (1부터 시작), y은 격자에서 찾을 수 있는 서로 다른 정사각형의 수이다.

아래 그림은 세 예제 케이스의 격자와 세 번째 예제 케이스에서 가능한 정사각형 하나를 보여 준다.