Độ khó: Trung bình (2/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

Có một khoảng sân hình chữ nhật kích thước ~2 \times n~ ô vuông, gồm 2 hàng và ~n~ cột. Đánh số hàng từ 1 đến 2 theo thứ tự từ trên xuống dưới, đánh số cột từ 1 đến ~n~ theo thứ tự từ trái qua phải. Người ta muốn lát sân bằng gạch màu trắng và điểm xuyết một số ô gạch màu đen, mỗi ô vuông được lát bởi một viên gạch, sao cho không có hai viên gạch màu đen nào chung cạnh với nhau. Hỏi có tất cả bao nhiêu cách khác nhau để lát khoảng sân trên (hai cách lát sân được gọi là khác nhau nếu tồn tại tối thiểu một ô ở dòng ~i~ cột ~j~ được lát gạch màu trắng ở cách này và lát gạch màu đen ở cách kia).

Ví dụ với ~n = 2~, ta có 7 cách lát sân.

Dữ liệu vào

• Là một số nguyên ~n~ ~(1 \le n \le 1000)~.

Kết quả

• Là số cách lát gạch khoảng sân theo yêu cầu trên. Số lượng này có thể rất lớn nên chỉ cần in ra 8 số cuối (mod ~100\,000\,000~).

Sample Input 1

2

Sample Output 1

7

Sample Input 2

1

Sample Output 2

3

Nguồn: NTUCoder (LAGA).