Đếm Cấu Hình Tường Lửa Trạm 5G

Mô tả

Kỹ sư An đang quản lý một tuyến truyền dẫn 5G chạy dọc theo quốc lộ, gồm N trạm phát sóng đánh số từ 1 đến N xếp thành một hàng dọc. Để bảo vệ an ninh mạng trước các cuộc tấn công điều khiển từ xa, An cần bật tính năng tường lửa cho một số trạm. Tuy nhiên, do ràng buộc về tài nguyên hệ thống, hai trạm kề nhau (ví dụ trạm 2 và trạm 3) không được phép cùng bật tường lửa cùng lúc, vì sẽ gây quá tải bộ xử lý tín hiệu tại cụm đó.

Hãy giúp An đếm số cách bật tường lửa thỏa mãn điều kiện trên. Một "cách" là một tập hợp các trạm được bật tường lửa. Tập rỗng (không bật trạm nào) cũng được tính là một cách hợp lệ. Vì kết quả có thể rất lớn, hãy trả về số dư khi chia cho 10007.

Đầu vào

• Một số nguyên dương N (1 ≤ N ≤ 10^5), là số lượng trạm phát sóng trên tuyến.

Đầu ra

• Một số nguyên duy nhất: số cách bật tường lửa thỏa mãn, lấy modulo 10007.

Ràng buộc

• 1 ≤ N ≤ 10^5.
• Mô-đun M = 10007.

Ví dụ

Ví dụ 1:

• Đầu vào: N = 3
• Đầu ra: 5

Giải thích: Có 3 trạm. Các cấu hình hợp lệ là:

1. Không bật trạm nào: {}
2. Chỉ bật trạm 1: {1}
3. Chỉ bật trạm 2: {2}
4. Chỉ bật trạm 3: {3}
5. Bật trạm 1 và 3 (không kề nhau): {1, 3}

Cấu hình {1, 2} bị loại vì trạm 1 và 2 kề nhau. Tổng cộng có 5 cách.

Ví dụ 2:

• Đầu vào: N = 1
• Đầu ra: 2

Giải thích: Có 1 trạm. Ta có thể bật hoặc không bật tường lửa cho nó, nên có 2 cách.