Tính tổ hợp nCr modulo 10^9+7 bằng Định lý Fermat nhỏ

Mục tiêu kiến thức

• Hiểu định nghĩa tổ hợp chập K của N: C(N, K) = N!K!(N-K)!.
• Áp dụng Định lý Fermat nhỏ để tính nghịch đảo modulo cho số nguyên tố P = 10⁹ + 7: a^-1 ≡ a^P-2 mod P.
• Tiền xử lý mảng giai thừa và nghịch đảo giai thừa trong O(N) để trả lời mỗi truy vấn tổ hợp trong thời gian O(1).

Mô tả bài toán

Hệ thống Gateway của AI Empire Academy cần xử lý Q truy vấn thống kê tổ hợp. Mỗi truy vấn gồm hai số nguyên N và K (0 ≤ K ≤ N ≤ 10⁶). Hãy tính giá trị C(N, K) mod 10⁹+7.

Quy ước nộp bài

• Chỉ cần viết một chương trình đọc stdin và in ra stdout. Bài này không yêu cầu viết hàm.
• Không dùng cout để in lời nhắc trước khi đọc dữ liệu. Lời nhắc sẽ lọt vào stdout và làm bài sai.
• Chỉ in đúng nội dung ở mục Output. Không in thêm nhãn, dòng trống hay ký tự thừa.
• Output được so khớp từng ký tự, phân biệt chữ hoa/thường và dấu câu.

Ràng buộc

• 1 ≤ Q ≤ 5 · 10⁵.
• 0 ≤ K ≤ N ≤ 10⁶.
• Thời gian chạy: 1000ms.
• Bộ nhớ tối đa: 256MB.