Perfect Attendance Award

At a school, each student's attendance record is checked at the end of the term to decide whether the student can receive a perfect attendance award. Each day in the record is marked as one of present O, late L, or absent A.

A student cannot receive the award in either of the following cases.

• The record contains at least two late days.
• The record contains three consecutive absent days.

When N is 4 days, the 43 records that can receive the award are as follows.

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

Given the number of days N in a term, compute how many attendance records can receive the award.

The first line contains an integer N. N is at most 1,000.

Print the number of attendance records that can receive the award, modulo 1,000,000.