🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📚 Mới ra mắt – Gói giải đề có lời giải chi tiết · chấm bài tự động · thầy hỗ trợ 1 – 1. Nếu còn phân vân về khóa học chính thức, các em và phụ huynh có thể tham khảo các gói giải đề dưới đây để trải nghiệm trước hệ thống làm bài, cách thầy phân tích – giải bài và sự hỗ trợ trực tiếp của thầy:

• 👉 Gói giải đề Tuyển sinh 10 chuyên Tin Hà Nội 2024 – 2026 – KHTN, ĐHSP · 5 đề · 21 bài · C++ và Python
• 👉 Gói giải đề Tuyển sinh 10 chuyên Tin Phổ thông Năng khiếu TP.HCM 2004 – 2026 – 22 đề · 84 bài · C++ và Python
• 👉 Gói giải đề HSG Tin học lớp 9 TP.HCM 2008 – 2026 – cấp Thành phố · 17 đề · 48 bài · C++ và Python
• 👉 Gói giải đề HSG Tin học lớp 9 Hà Nội 2005 – 2026 – cấp Thành phố · 17 đề · 69 bài · C++ và Python

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Mùa nước nổi năm nay, thầy Sơn thả cá linh trong một cái đìa nhỏ sát bờ sông Hậu. Giữa đìa thầy cắm một cây sào có khắc vạch ~0, 1, 2, \ldots, H~ để theo dõi mực nước. Mực nước luôn là một số nguyên và phải luôn nằm trong khoảng từ ~1~ đến ~H - 1~: xuống tới vạch ~0~ là đìa cạn, cá chết; lên tới vạch ~H~ là nước tràn bờ, cá theo nước ra sông hết.

Theo kinh nghiệm của dân miền Tây, con nước thay đổi theo từng giờ, mỗi giờ chỉ có đúng một trong ba khả năng:

• nước lớn: mực nước tăng ~1~ vạch;
• nước ròng: mực nước giảm ~1~ vạch;
• nước đứng: mực nước giữ nguyên.

Một kịch bản con nước trong ~N~ giờ là một dãy gồm ~N~ lựa chọn như trên (giờ thứ nhất, giờ thứ hai, ..., giờ thứ ~N~). Kịch bản được gọi là an toàn nếu sau mỗi giờ (kể cả giờ cuối cùng) mực nước vẫn nằm trong đoạn ~[1, H - 1]~.

Thầy Sơn đang lên kế hoạch cho ~Q~ đợt nuôi khác nhau, đợt nuôi thứ ~i~ bắt đầu khi mực nước ở vạch ~A_i~ và thầy muốn sau đúng ~N~ giờ mực nước ở vạch ~B_i~ (để kịp tháo nước bắt cá). Với mỗi đợt nuôi, hãy giúp thầy Sơn đếm số kịch bản con nước an toàn bắt đầu ở ~A_i~ và kết thúc ở ~B_i~. Vì kết quả có thể rất lớn, chỉ cần in ra phần dư khi chia cho ~10^9 + 7~.

Dữ liệu vào

• Dòng đầu tiên chứa ba số nguyên ~N, H, Q~ ~(1 \le N \le 10^6;~ ~2 \le H \le 10^6;~ ~1 \le Q \le 2 \times 10^5)~.
• ~Q~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~A_i, B_i~ ~(1 \le A_i, B_i \le H - 1)~.

Kết quả

Gồm ~Q~ dòng, dòng thứ ~i~ là số kịch bản con nước an toàn của đợt nuôi thứ ~i~, lấy theo modulo ~10^9 + 7~.

Giới hạn (Subtask)

• Subtask 1 (~20\%~ số điểm): ~N, H, Q \le 300~.
• Subtask 2 (~20\%~ số điểm): ~N \le 5000~ và ~H > N~.
• Subtask 3 (~30\%~ số điểm): ~H > N~.
• Subtask 4 (~30\%~ số điểm): không có ràng buộc gì thêm.

💡 Lưu ý khi nộp bằng Python: các em nên chọn ngôn ngữ PyPy 3 thay vì Python 3 để chương trình chạy nhanh hơn nhiều. Giới hạn thời gian cho Python/PyPy ở bài này là 5 giây (C++: 1 giây).

Sample Input 1

3 3 2
1 1
1 2

Sample Output 1

4
4

Giải thích

Mực nước chỉ được là ~1~ hoặc ~2~: ở vạch ~1~ không được nước ròng (cạn đìa), ở vạch ~2~ không được nước lớn (tràn bờ). Hình dưới liệt kê đủ ~8~ kịch bản an toàn bắt đầu ở vạch ~1~: có ~4~ kịch bản kết thúc ở vạch ~1~ và ~4~ kịch bản kết thúc ở vạch ~2~.

Sample Input 2

4 5 3
1 1
2 4
4 1

Sample Output 2

9
9
4

Giải thích

• Đợt ~1~: có ~9~ kịch bản, chẳng hạn đứng – đứng – đứng – đứng hoặc lớn – ròng – lớn – ròng.
• Đợt ~2~: kịch bản lớn – đứng – lớn – đứng ~(2 \to 3 \to 3 \to 4 \to 4)~ là an toàn; còn kịch bản lớn – lớn – lớn – ròng ~(2 \to 3 \to 4 \to 5 \to 4)~ tuy cũng kết thúc ở vạch ~4~ nhưng sau giờ thứ ~3~ nước lên tới vạch ~5 = H~ (tràn bờ) nên không an toàn. Tổng cộng có ~9~ kịch bản an toàn.
• Đợt ~3~: phải giảm ~3~ vạch trong ~4~ giờ nên gồm ~3~ giờ nước ròng và ~1~ giờ nước đứng; giờ nước đứng có ~4~ vị trí để chọn, nên có ~4~ kịch bản.

Nguồn: Đề tự luyện HSG Tin học quốc gia (đề tự soạn).