인트라넷

Apricot Rules LLC는 새로운 단순화된 네트워킹 프로토콜을 개발하고 있으며, 자신들의 라우팅 알고리즘을 선보이고 싶어 한다. 이들의 설계에서 네트워크는 $1$부터 $\mathbf{M}$까지 번호가 매겨진 $\mathbf{M}$대의 머신으로 구성되며, 모든 머신 쌍은 직접 링크로 연결된다. 각 링크에는 $1$에서 $(\mathbf{M} \times (\mathbf{M} - 1) / 2)$ 사이의 고유한 정수 우선순위 값이 주어지고, 각 머신은 그 우선순위에 따라 트래픽을 라우팅한다.

안타깝게도 라우팅 알고리즘이 너무 공격적이어서, 한 머신의 모든 트래픽을 그 머신에 연결된 링크 중 우선순위가 가장 높은 링크를 통해 라우팅한다. 이로 인해 일부 머신 그룹이 다른 그룹들로부터 고립될 수 있다.

형식적으로, $\ell$가 $m$에 연결된 링크 중 우선순위가 가장 높은 링크일 때, 그리고 그럴 때에만 머신 $m$가 링크 $\ell$를 사용한다고 한다. 또한 링크가 연결하는 두 머신 중 적어도 하나가 그 링크를 사용하면 그 링크가 활성 상태라고 한다. 링크 우선순위가 주어지면 원래 네트워크는 서로 겹치지 않는 인트라넷들로 분할된다. 두 머신 사이에 활성 링크만 사용하는 어떤 경로가 있을 때, 그리고 그럴 때에만 두 머신은 같은 인트라넷에 속한다.

예를 들어 위의 왼쪽 그림에서 볼 수 있듯이 우선순위가 $6$와 $5$인 링크만 활성 상태이다. 이로 인해 서로 겹치지 않는 두 인트라넷이 생긴다. 그러나 오른쪽 예제에서는 세 링크가 활성 상태이므로, $4$대의 머신 모두로 구성된 하나의 인트라넷이 생긴다.

Apricot Rules LLC의 품질 보증 팀원인 당신은 이 문제의 심각성을 조사하고 있다. 우선순위를 배정하는 $(\mathbf{M} \times (\mathbf{M} - 1) / 2)!$가지 방법 중 하나를 균등한 확률로 무작위 선택하여 우선순위를 배정할 때, 인트라넷이 정확히 $\mathbf{K}$개 존재할 확률을 알고자 한다.

제한

메모리 제한: 1 GB. $1 \le \mathbf{T} \le 50$. $1 \le \mathbf{K} \le \mathbf{M} / 2$.

테스트 세트 1 (Visible Verdict)

시간 제한: 20초. $2 \le \mathbf{M} \le 50$.

테스트 세트 2 (Hidden Verdict)

시간 제한: 60초. $2 \le \mathbf{M} \le 5 \times 10^5$.

입력의 첫 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다. 각 테스트 케이스는 머신의 수와 목표 인트라넷 수를 각각 나타내는 두 정수 $\mathbf{M}$와 $\mathbf{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에서 다음 상황을 생각해 보자. $\mathbf{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\}$가 존재한다. $\mathbf{K} = 2$이므로 이 상황은 정답에 포함된다.

$10! = 3628800$가지 방법 중 정확히 $2$개의 인트라넷이 생기도록 우선순위를 배정하는 방법이 $1555200$가지임을 알 수 있으므로, 확률은 $3/7$이다.

예제 케이스 #2에서 확률은 $4/7$이다.

예제 케이스 #3에서 확률은 $1/21$이다.