Bậc thang truyền tín hiệu

Bối cảnh và bài toán

Một bộ điều khiển có n mức tín hiệu. Từ mức 0, mỗi thao tác chỉ có thể tăng thêm 1 hoặc 2 mức. Hai chuỗi thao tác khác nhau được xem là hai phương án khác nhau.

Yêu cầu

Tính số phương án để đạt đúng mức n, lấy modulo 10^9+7.

Input

Một dòng chứa n.

Output

In số phương án modulo 10^9+7.

Ràng buộc

• 1 <= n <= 10^6

Chấm điểm

Ví dụ 1

Input

1

Output

1

Giải thích. Ví dụ nhỏ giúp kiểm tra cách mô hình hóa trạng thái và kết quả cuối; khi tự giải, cần suy luận từ ràng buộc thay vì suy đoán từ sample.

Ví dụ 2

Input

2

Output

2

Giải thích. Hãy đối chiếu với edge case: trạng thái đầu, trạng thái không đạt được, tie hoặc biên chỉ số tùy bài.

Gợi ý

Trước khi code, hãy viết rõ ý nghĩa của trạng thái, các trạng thái tiền nhiệm và thứ tự tính sao cho mọi dependency đã có giá trị.

Thông tin bài tập

Nguồn: FULLHOUSE DEV – Self-generated.