Giải thưởng

Điểm: 1,10 (OI)

Giới hạn thời gian: 3.0s

Giới hạn bộ nhớ: 512M

Input: stdin

Output: stdout

Nguồn bài:

HSPC 2014

Dạng bài

Ngôn ngữ cho phép

C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Một trường Công Nghệ trao tiền thưởng cho học sinh đi học đầy đủ và đúng giờ. Nếu vắng mặt trong ba ngày liên tiếp hoặc đi muộn nhiều hơn một lần thì sinh viên sẽ bị tịch thu tiền thưởng. Trong suốt khoảng thời gian ~N~ ngày, "bản điểm danh" của một học sinh là một chuỗi ~N~ ký tự ~L~ (muộn), ~O~ (đúng giờ), và ~A~ (vắng mặt). Mặc dù có ~81~ chuỗi trong suốt ~4~ ngày có thể được tạo ra, chính xác ~43~ chuỗi sẽ dẫn đến giải thưởng:

~OOOO \ OOOA \ OOOL \ OOAO \ OOAA \ OOAL \ OOLO \ OOLA \ OAOO \ OAOA \ OAOL \ OAAO \ OAAL \ OALO \ OALA \ OLOO \ OLOA~

~OLAO \ OLAA \ AOOO \ AOOA \ AOOL \ AOAO \ AOAA \ AOAL \ AOLO \ AOLA \ AAOO \ AAOA \ AAOL \ AALO \ AALA \ ALOO \ ALOA~

~ALAO \ ALAA \ LOOO \ LOOA \ LOAO \ LOAA \ LAOO \ LAOA \ LAAO~

Hỏi có bao nhiêu chuỗi "giải thưởng" tồn tại sau một khoảng thời gian ~N~ ngày?.

Input

Gồm nhiều test, mỗi test nằm trên một dòng gồm ~1~ số nguyên ~N \leq 3000~.

Output

Với mỗi test, in ra trên một dòng kết quả phải tính.

Sample Input

Sample Output

Bình luận

Hãy đọc nội quy trước khi bình luận.

Không có bình luận tại thời điểm này.