11031번 - GIẢI THƯỞNG 다국어

문제

Một trường Công Nghệ trao tiền thưởng cho học sinh đi học đầy đủ và đúng giờ. Nếu vắng mặt trong ba ngày liên tiếp hoặc đi muộn nhiều hơn một lần thì sinh viên sẽ bị tịch thu tiền thưởng.

Trong suốt khoảng thời gian N ngày, “bản điểm danh” của một học sinh là một chuỗi N ký tự L (muộn), O (đúng giờ), và A (vắng mặt).

Mặc dù có 81 chuỗi trong suốt 4 ngày có thể được tạo ra, chính xác 43 chuỗi sẽ dẫn đến giải thưở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 

Hỏi có bao nhiêu chuỗi "giải thưởng" tồn tại sau một khoảng thời gian N ngày?

입력

Gồm nhiều test, mỗi test nằm trên một dòng gồm 1 số nguyên N ≤ 3000

출력

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

제한

힌트