Attendance Award

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?

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.

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.