문제

학교는 정기적으로 제 시간에 출석하는 학생에게 상을 줍니다.

연속 3일을 결석하거나 총 2회 이상 지각할 경우 상을 받을 수 없습니다.

N일 동안 학생의 출석 여부를 L(지각), O(출석), A(결석)으로 적을 수 있습니다.

4일 동안 가능한 출석 상태의 가짓수는 총 81가지이나 이 중 상을 받을 수 있는 출석 상태는 총 43가지입니다.

N일 후에 상을 받을 수 있는 경우는 총 몇 가지입니까?

입력

한 줄에 하나씩 여러 줄에 걸쳐 정수 N (N<=3000)이 들어옵니다.

출력

각 입력에 대해 답을 한 줄에 하나씩 출력합니다.