가족 호텔

제한

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

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

2 ≤ N ≤ $10^{4}$.

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

2 ≤ N ≤ $10^{7}$.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 줄이 주어진다. 각 줄에는 방의 수 N과 우리가 관심을 두는 방 번호 K, 이렇게 두 수가 주어진다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x은 1부터 시작하는 테스트 케이스 번호이고, y은 구하려는 확률을 $10^{9}$+7로 나눈 나머지이며, 이는 다음과 같이 정확히 정의된다. 방 K가 사용 중일 확률을 기약분수 p/q로 나타낸다. 그러면 수 y은 합동식 y × q ≡ p (mod 10^{9}+7)을 만족해야 하며, 0 이상 $10^{9}$+6 이하이어야 한다. 이 문제의 제한 조건에서는 그러한 수 y이 항상 존재하며 유일하게 결정됨을 보일 수 있다.

예제 케이스 #3에는 방이 네 개 있으며, 첫 번째 방이 사용 중일 확률을 구한다. 첫 번째 가족이 도착하면 가능한 상황은 3가지이고, 각 상황의 확률은 1/3이다. 각 상황에서는 방 1+2, 2+3, 또는 3+4를 사용한다. 첫 번째 상황에서는 첫 번째 방이 이미 사용 중이며 계속 사용 중으로 남는다. 두 번째 상황에서는 첫 번째 방이 비어 있고 더 이상 어떤 가족도 수용할 수 없으므로 계속 빈 상태로 남는다. 마지막으로 세 번째 상황에서는 다음에 도착하는 가족이 반드시 방 1+2를 배정받으므로 첫 번째 방이 사용 중이 된다. 따라서 첫 번째 방이 사용 중일 확률은 2/3이고, (666666672 * 3) mod 1000000007 = 2 mod 1000000007이므로 답은 666666672이다.

예제 케이스 #1의 확률은 1/2이고, 예제 케이스 #2와 #4의 확률은 1이다.