정사각형 세기

Mr. Panda는 최근 Square Off라는 새 게임에 빠졌다. 이 게임에서 플레이어들은 일정한 간격으로 배치된 직사각형 격자 점들 위에서 서로 다른 정사각형을 최대한 많이 찾아 겨룬다. 정사각형을 찾으려면 정사각형의 네 꼭짓점을 이루는 점 네 개를 찾아야 한다. 물론 정사각형의 네 변의 길이는 모두 같아야 하지만, 그 길이가 얼마인지는 상관없고 정사각형이 격자 축에 나란히 정렬되어 있을 필요도 없다. 이렇게 찾은 서로 다른 정사각형마다 1점을 얻는다. 두 정사각형은 네 점의 집합이 다를 때, 그리고 그때만 서로 다르다.

Mr. Panda는 점이 R개의 행과 C개의 열로 놓인 격자를 받았다. 이 격자에서 서로 다른 정사각형을 몇 개나 찾을 수 있을까? 답이 매우 클 수 있으니 109 + 7 (1000000007)로 나눈 나머지를 출력하라.

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

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

• 1 ≤ T ≤ 100.

아래 그림은 세 가지 샘플 케이스의 격자와 세 번째 샘플 케이스에서 유효한 정사각형 하나를 나타낸다.