경우의 수를 세어 보자

Googleland의 기념일을 축하하기 위해 N쌍의 커플이 노 젓는 배를 타러 간다. 배는 매우 길지만 한 사람 너비밖에 되지 않으므로, 사람들은 앞에서 뒤까지 한 줄로 앉는다.

하지만 항해를 예행연습하는 동안 배가 움직이지 않았다! 조사한 결과, 주최 측은 일부 신혼부부들이 노를 젓지 않고 내내 서로를 위한 사랑의 시를 쓰고 있었다는 사실을 알아냈다. 구체적으로 신혼부부는 M쌍이다. 한 신혼부부의 두 구성원이 서로 옆에 앉으면, 시를 쓰느라 너무 바빠서 노를 젓지 않는다.

이제 주최 측은 Googleland에서 가장 똑똑한 사람인 여러분에게, M쌍의 신혼부부 각각에 대해 두 구성원이 서로 옆에 앉지 않도록 총 2N명의 사람을 배에 배치하는 가능한 방법이 몇 가지인지 묻는다. 배의 어떤 위치에서 두 방법에 서로 다른 사람이 배치되어 있다면 두 방법은 서로 다르다. 방법의 수를 셀 때 커플의 두 구성원은 서로 바꿔도 같은 것으로 간주되지 않는다는 점에 유의한다. 그 수는 매우 클 수 있으므로, 주최 측은 답을 1000000007($10^{9}$+7)로 나눈 나머지만 알고 싶어 한다.

제한

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

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

1 ≤ M ≤ N ≤ 100.

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

1 ≤ M ≤ N ≤ 100000.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 위에서 설명한 두 정수 N과 M이 적힌 한 줄로 이루어진다.

각 테스트 케이스마다 Case #x: y를 포함하는 한 줄을 출력한다. 여기서 x는 1부터 시작하는 테스트 케이스 번호이고, y는 가능한 배치의 수를 1000000007($10^{9}$+7)로 나눈 나머지이다.

예제 케이스 #1에는 커플이 2쌍 있다. 설명을 간단하게 하기 위해 문자 A와 a로 신혼부부를 나타내고, B와 b로 다른 커플을 나타낸다. 문제의 규칙에 따라 A와 a는 서로 인접할 수 없다. 네 사람을 배치하는 방법은 12가지이다: ABab ABba AbaB AbBa aBAb aBbA abAB abBA BAba BabA bABa baBA

예제 케이스 #2에서는 두 커플 모두 신혼부부이므로, A와 a는 서로 인접할 수 없고, B와 b도 서로 인접할 수 없다. 이들은 다음 8가지 방법으로 배치될 수 있다: ABab AbaB aBAb abAB BAba BabA bABa baBA