Bạn điều hành một khách sạn có \(N\) phòng nằm dọc theo một hành lang dài, được đánh số từ 1 đến \(N\). Khách của bạn là những đại gia đình, và mỗi gia đình khi đến đều yêu cầu đúng hai phòng kề nhau. Hai phòng được coi là kề nhau nếu số phòng chênh nhau đúng 1.

Đầu ngày hôm nay, khách sạn hoàn toàn trống. Bạn dùng chiến lược đơn giản sau để xếp phòng. Mỗi khi một gia đình đến, bạn xét tất cả các cặp phòng kề nhau mà cả hai phòng đều còn trống, chọn ngẫu nhiên đều một cặp trong số đó, rồi giao hai phòng ấy cho gia đình. Các gia đình liên tục đến, mỗi lần một gia đình; nhưng ngay khi không còn cặp phòng kề nhau nào cùng trống, bạn bật biển HẾT PHÒNG và không giao thêm phòng nữa.

Với một số phòng cụ thể, xác suất để phòng đó đã có người ở vào lúc bạn bật biển HẾT PHÒNG là bao nhiêu?

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Tiếp theo là \(T\) dòng; mỗi dòng chứa hai số: số phòng \(N\) và số hiệu phòng \(K\) mà ta quan tâm.

Dữ liệu ra

Với mỗi bộ test, in một dòng Case #x: y, trong đó x là số thứ tự bộ test (bắt đầu từ 1), còn y là xác suất cần tìm tính theo modulo \(10^9+7\), được định nghĩa chính xác như sau.

Biểu diễn xác suất phòng \(K\) có người ở dưới dạng phân số tối giản p/q. Khi đó y phải thỏa mãn

và nằm trong đoạn từ 0 đến \(10^9+6\), kể cả hai đầu. Có thể chứng minh rằng dưới các ràng buộc của bài, y luôn tồn tại và được xác định duy nhất.

Ràng buộc

• \(1 \le T \le 100\).
• \(1 \le K \le N\).

Phân nhóm

• Test Set 1 (Hiển thị): \(2 \le N \le 10^4\).
• Test Set 2 (Ẩn): \(2 \le N \le 10^7\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

4
3 1
3 2
4 1
4 2

Case #1: 500000004
Case #2: 1
Case #3: 666666672
Case #4: 1

Nguồn

Google Code Jam 2016, Chung kết thế giới, bài Family Hotel.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.