Attendance Award

Interview

Time limit1sMemory limit256 MB

Summary

Count length-N strings over L, O and A with at most one L and no three consecutive As for each N up to 3000.

Level: Medium5 of 10
Topics: Dynamic programming, Combinatorics
Solved: No attempts yet

Problem

A school of engineering pays a prize to students who miss few classes and are rarely late. A student loses the prize by being absent on three days in a row, or by being late more than once.

Over a span of $N$ days a student's attendance record is a string of $N$ characters, each one L (late), O (on time), or A (absent).

There are 81 records covering four days, and exactly 43 of them win the prize.

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

How many records covering $N$ days win the prize?

Input

The input holds several tests. Each line holds one integer $N$ ( $1 \le N \le 3000$ ). The input ends at the end of the file.

Output

For each test, print the number of winning records on a line of its own. The count grows very large, so print it in full without taking any remainder.

Examples3

Example 1
Input
```
4
```
Expected output
```
43
```
Example 2
Input
```
1
```
Expected output
```
3
```

Example 3

Input

Expected output