Perfect Attendance Award

Interview

Time limit2sMemory limit128 MB

Summary
Count length-N attendance strings over O, L, A that have at most one L and no three consecutive A's, modulo 1,000,000.
Level

Medium4 of 10

Topics
Dynamic programming, String, Combinatorics
Solved
No attempts yet

Problem

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.

Input

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

Output

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

Examples1

  1. Example 1

    Input
    4
    Expected output
    43