Độ khó: Khá (3/4 điểm)

📖 Bài giải chi tiết: 👉 Bấm vào đây để xem lời giải cụ thể của bài này trên blog

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới bấm vào xem bài giải nhé!

🎓 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

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

---

Bài toán được chuyển sang dạng nhập/xuất chuẩn (stdin/stdout); định dạng xem ở mục Dữ liệu vào.

Có ~n~ phòng bạn cần đến thăm, được đánh số từ ~0~ đến ~n - 1~. Các ngày cũng được đánh số, bắt đầu từ ~0~. Mỗi ngày bạn sẽ vào thăm đúng một phòng.

Ban đầu, vào ngày ~0~, bạn thăm phòng ~0~. Thứ tự thăm các phòng ở những ngày tiếp theo được xác định bởi các quy tắc sau cùng với một mảng nextVisit độ dài ~n~ (đánh số từ 0):

• Giả sử vào một ngày nào đó bạn thăm phòng ~i~,
  • nếu bạn đã vào phòng ~i~ một số lẻ lần (tính cả lần hiện tại) thì vào ngày tiếp theo bạn sẽ thăm phòng nextVisit[i], trong đó ~0 \le~ nextVisit[i] ~\le i~;
  • nếu bạn đã vào phòng ~i~ một số chẵn lần (tính cả lần hiện tại) thì vào ngày tiếp theo bạn sẽ thăm phòng ~(i + 1) \bmod n~.

Hãy in ra số thứ tự của ngày đầu tiên mà bạn đã từng ở trong tất cả các phòng. Có thể chứng minh rằng ngày như vậy luôn tồn tại. Vì đáp án có thể rất lớn, hãy in ra nó theo modulo ~10^9 + 7~.

Dữ liệu vào

• Dòng đầu là số nguyên ~n~.
• Dòng thứ hai gồm ~n~ số nguyên nextVisit[0], nextVisit[1], ..., nextVisit[n-1].

Kết quả

• Một số nguyên là số thứ tự ngày cần tìm, lấy modulo ~10^9 + 7~.

Giới hạn

• ~2 \le n \le 10^5~.
• ~0 \le~ nextVisit[i] ~\le i~.

Sample Input 1

2
0 0

Sample Output 1

2

Giải thích

• Ngày 0, bạn thăm phòng 0. Tổng số lần bạn đã vào phòng 0 là 1, là số lẻ. Ngày tiếp theo bạn sẽ thăm phòng nextVisit[0] = 0.
• Ngày 1, bạn thăm phòng 0. Tổng số lần bạn đã vào phòng 0 là 2, là số chẵn. Ngày tiếp theo bạn sẽ thăm phòng ~(0 + 1) \bmod 2 = 1~.
• Ngày 2, bạn thăm phòng 1. Đây là ngày đầu tiên bạn đã ở trong tất cả các phòng.

Sample Input 2

3
0 0 2

Sample Output 2

6

Giải thích

Thứ tự phòng bạn thăm theo từng ngày là [0,0,1,0,0,1,2,...]. Ngày 6 là ngày đầu tiên bạn đã ở trong tất cả các phòng.

Sample Input 3

4
0 1 2 0

Sample Output 3

6

Giải thích

Thứ tự phòng bạn thăm theo từng ngày là [0,0,1,1,2,2,3,...]. Ngày 6 là ngày đầu tiên bạn đã ở trong tất cả các phòng.

Nguồn: LeetCode 1997.