인트라넷

Apricot Rules LLC는 새로운 단순 네트워크 프로토콜을 개발하고 있으며, 이 회사의 라우팅 알고리즘을 선보이고자 한다. 이 설계에서 네트워크는 1부터 $M$까지 번호가 붙은 $M$개의 머신으로 이루어지고, 머신의 모든 쌍은 직접 연결된 링크로 이어진다. 각 링크에는 $1$부터 $M(M-1)/2$ 사이의 서로 다른 정수 우선순위가 주어지며, 각 머신은 이 우선순위에 따라 트래픽을 보낸다.

안타깝게도 이 라우팅 알고리즘은 지나치게 공격적이다. 머신에서 나가는 모든 트래픽을 그 머신에 연결된 가장 높은 우선순위의 링크로 보낸다. 그 결과 일부 머신 그룹이 나머지 머신들과 고립될 수 있다.

정확히 말하면, 머신 $m$은 링크 $\ell$이 $m$에 연결된 링크 중 가장 높은 우선순위를 가질 때, 그리고 그때에만 $\ell$을 사용한다. 링크는 연결하는 두 머신 중 적어도 한 머신이 사용하면 활성 상태이다. 원래 네트워크는 서로소인 인트라넷들로 나뉜다. 두 머신은 활성 링크만 이용한 경로가 존재할 때, 그리고 그때에만 같은 인트라넷에 속한다.

위 그림의 왼쪽을 보면 우선순위가 $6$과 $5$인 링크만 활성 상태이며, 그래서 서로소인 인트라넷이 두 개 생긴다. 오른쪽 예에서는 활성 링크가 세 개이므로 4개의 머신 전체가 하나의 인트라넷을 이룬다.

Apricot Rules LLC 품질 보증팀의 일원으로서, 이 문제가 얼마나 심각한지 조사하고 있다. 우선순위를 $(M(M-1)/2)!$가지 방법 중에서 균등한 확률로 무작위 배정할 때, 인트라넷이 정확히 $K$개가 되는 확률을 구하라.

입력의 첫 줄에는 테스트 케이스의 개수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다. 각 테스트 케이스는 한 줄로 되어 있으며, 두 정수 $M$과 $K$가 차례로 주어진다. $M$은 머신의 개수이고 $K$는 목표 인트라넷 개수이다.

각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력한다. 여기서 $x$는 테스트 케이스 번호(1부터 시작)이고, $y$는 구하는 확률을 소수 $10^9+7$($1000000007$)로 나눈 나머지이다. 확률은 기약분수 $p/q$로 나타내며, $p$와 $q$는 $p+q$가 최소가 되는 음이 아닌 정수이다. 그러면 $y$는 $p \cdot q^{-1} \bmod (10^9+7)$과 같아야 한다. 여기서 $q^{-1}$은 법 $10^9+7$에 대한 $q$의 곱셈 역원이다. 이 문제의 제약 아래에서 그러한 $y$가 항상 존재하며 유일함을 보일 수 있다.

• $1 \le T \le 50$.
• $1 \le K \le M/2$.

샘플 케이스 #1에서 다음 상황을 생각해 보자. $M=5$인 머신을 $1, 2, 3, 4, 5$라고 하고, 머신 $a$와 머신 $b$를 잇는 링크를 $(a,b)$로 표기한다. 링크 $(1,2), (1,3), (1,4), (1,5), (2,3), (2,4), (2,5), (3,4), (3,5), (4,5)$의 우선순위가 각각 $9, 8, 7, 6, 5, 4, 3, 2, 1, 10$이라고 가정하자. 그러면 머신 1과 2는 링크 $(1,2)$를, 머신 3은 링크 $(1,3)$을, 머신 4와 5는 링크 $(4,5)$를 사용한다. 따라서 활성 링크는 $(1,2), (1,3), (4,5)$ 세 개이고, 인트라넷은 $\{1,2,3\}$과 $\{4,5\}$ 두 개이다. $K=2$이므로 이 상황은 답에 포함된다.

$10!=3628800$가지 우선순위 배정 중 인트라넷이 정확히 2개가 되는 경우는 $1555200$가지이므로, 확률은 $3/7$이다. 샘플 케이스 #2의 확률은 $4/7$이고, 샘플 케이스 #3의 확률은 $1/21$이다.