개근상

면접 대비

시간 제한1초메모리 제한256 MB

요약

L이 최대 한 번 나오고 A가 세 번 연속되지 않는 길이 N 문자열 개수를 각 테스트마다 구합니다.

난이도: 보통10점 중 5점
유형: 동적 계획법, 조합론
정답자: 아직 제출이 없습니다

문제

어느 공과대학은 결석과 지각이 적은 학생에게 상금을 준다. 사흘 연속으로 결석하거나 지각을 두 번 넘게 하면 상금을 받지 못한다.

$N$ 일 동안의 출석 기록은 L(지각), O(정시 출석), A(결석) 세 문자로 이루어진 길이 $N$ 의 문자열이다.

4일치 출석 기록은 모두 81가지지만, 그중 상금을 받는 기록은 정확히 43가지다.

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

$N$ 일 동안의 출석 기록 중 상금을 받는 기록이 몇 가지인지 구하라.

입력

입력은 여러 개의 테스트로 이루어진다. 각 줄에 정수 $N$ ( $1 \le N \le 3000$ )이 하나씩 주어진다. 입력은 파일 끝에서 끝난다.

출력

각 테스트마다 상금을 받는 출석 기록의 개수를 한 줄에 하나씩 출력한다. 개수가 매우 커질 수 있으니 나머지 연산 없이 그대로 출력한다.

예제3

예제 1
입력
```
4
```
예상 출력
```
43
```
예제 2
입력
```
1
```
예상 출력
```
3
```

예제 3

입력

예상 출력