가족 호텔 (Large)

당신은 긴 복도 하나를 따라 방 $N$개가 늘어선 호텔을 운영한다. 방에는 복도를 따라 1번부터 $N$번까지 번호가 붙어 있다. 손님은 모두 대가족이어서 가족마다 도착하면 서로 인접한 방 두 개를 요청한다. 두 방의 번호 차이가 정확히 1이면 두 방은 인접한다.

오늘 하루가 시작될 때 호텔은 비어 있었다. 당신은 다음과 같은 간단한 방법으로 손님에게 방을 배정해 왔다. 가족이 한 팀 도착할 때마다 두 방이 모두 비어 있는 인접한 방 쌍을 전부 살펴보고, 그중 하나를 균등한 확률로 무작위로 골라 그 두 방을 그 가족에게 배정한다. 새 가족은 한 번에 한 팀씩 끊임없이 도착한다. 하지만 두 방이 모두 비어 있는 인접한 방 쌍이 더 이상 없으면 만실(NO VACANCY) 표시를 켜고 더는 방을 내주지 않는다.

방 번호 $K$가 주어질 때, 만실 표시를 켜는 시점에 그 방이 사용 중일 확률을 구하라.

첫째 줄에 테스트 케이스의 수 $T$가 주어진다. 이어서 $T$개의 줄이 주어지며, 각 줄에는 방의 수 $N$과 확률을 구할 방 번호 $K$가 주어진다.

제한

• $1 \le T \le 100$
• $1 \le K \le N$
• $2 \le N \le 10^7$

각 테스트 케이스마다 Case #x: y 형식으로 한 줄을 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, y는 구하는 확률을 $10^9+7$로 나눈 나머지로, 정확한 정의는 다음과 같다. 방 $K$가 사용 중일 확률을 기약분수 $p/q$로 나타낸다. 이때 $y$는 모듈러 방정식 $y \times q \equiv p \pmod{10^9+7}$을 만족하고 0 이상 $10^9+6$ 이하인 수이다. 이 문제의 제한에서는 이러한 $y$가 항상 존재하고 유일하게 정해짐을 보일 수 있다.

예제의 3번 케이스에서는 방이 4개이고 1번 방이 사용 중일 확률을 구한다. 첫 가족이 도착하면 방 1+2, 2+3, 3+4 중 하나를 각각 1/3의 확률로 차지한다. 첫 번째 경우에는 1번 방이 이미 사용 중이고 끝까지 그대로다. 두 번째 경우에는 1번 방이 비어 있고 더 받을 수 있는 가족이 없으므로 1번 방은 끝까지 비어 있다. 세 번째 경우에는 다음 가족이 반드시 방 1+2를 받으므로 1번 방이 사용 중이 된다. 따라서 1번 방이 사용 중일 확률은 2/3이고, (666666672 * 3) mod 1000000007 = 2 mod 1000000007이므로 답은 666666672이다.

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