Petar chọn ngẫu nhiên và độc lập \(n\) số nguyên từ \(1\) đến \(k\), tạo thành mảng \(a\). Mảng \(a\) được gọi là cấu trúc khi đồng thời thỏa hai điều kiện: mỗi số từ \(1\) đến \(n\) xuất hiện đúng một lần trong mảng; và với mọi chỉ số \(i\) (\(1\le i\le n\)), có \(|a_i+i-n-1|\le1\). Hãy tính xác suất để mảng ngẫu nhiên là một cấu trúc.

Dữ liệu vào

Dòng đầu chứa hai số nguyên \(n,k\) (\(1\le n,k\le10^9\)).

Dữ liệu ra

Có thể biểu diễn xác suất dưới dạng phân số tối giản \(P/Q\), trong đó \(Q\) không chia hết cho \(10^9+7\). In \(P\cdot Q^{-1}\pmod {10^9+7}\).

Ràng buộc

Các giới hạn chính thức được nêu trong phần Dữ liệu vào.

Phân nhóm

1. \(17\) điểm: \(n,k\le7\).
2. \(23\) điểm: \(n\le7\), \(k\le100\).
3. \(19\) điểm: \(n\le20\), \(k\le100\).
4. \(25\) điểm: \(n,k\le10^6\).
5. \(26\) điểm: không có ràng buộc thêm.

Ví dụ

2 1

0

2 2

500000004

7 94

100976822

Nguồn

COCI 2025/2026 - Vòng 5, bài Struktura.

Đề bài, dữ liệu kiểm thử và lời giải tham khảo được lấy từ nguồn chính thức của Croatian Open Competition in Informatics.