Let Me Count The Ways

Googleland의 기념일을 맞아 N쌍의 커플이 보트를 타고 놀러 가려고 한다. 보트는 아주 길지만 한 사람의 폭밖에 되지 않아서, 사람들은 앞에서 뒤로 일렬로 앉게 된다.

그런데 여행 연습 도중 보트가 움직이지 않았다! 조사 결과, 신혼부부 몇 쌍이 노를 젓지 않고 서로에게 사랑의 시를 쓰고 있었던 것이다. 구체적으로 M쌍의 신혼부부가 있다. 신혼부부의 두 사람이 서로 옆에 앉아 있으면, 그들은 시를 쓰느라 바빠서 노를 젓지 않는다.

이제 조직자들이 Googleland에서 가장 똑똑한 당신에게 와서 묻는다. M쌍의 신혼부부 각각에 대해 두 사람이 서로 옆에 앉지 않도록, 2N명의 사람을 보트에 배치하는 방법은 몇 가지인가? 두 방법은 보트의 어떤 위치에서 서로 다른 사람을 사용하면 서로 다른 방법이다. 방법의 수를 셀 때 커플의 두 사람은 서로 바꿀 수 있는 것으로 취급하지 않는다. 답이 매우 클 수 있으므로, 조직자들은 답을 1000000007(10^9+7)로 나눈 나머지만 알고 싶어 한다.

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

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

• 1 ≤ T ≤ 100.