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 OAOAOAOL OAAO OAAL OALO OALA OLOO OLOA OLAO OLAA AOOOAOOA AOOL AOAO AOAA AOAL AOLO AOLA AAOO AAOA AAOLAALO AALA ALOO ALOA ALAO ALAA LOOO LOOA LOAO LOAALAOO 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.