개근상

어느 학교에서는 학기 말에 학생의 출결 기록을 보고 개근상을 받을 수 있는지 판단한다. 출결 기록의 각 날은 출석 O, 지각 L, 결석 A 중 하나로 표시된다.

개근상을 받을 수 없는 경우는 다음 두 가지이다.

• 지각이 두 번 이상인 경우
• 결석이 세 번 연속으로 나타나는 경우

N이 4일일 때 개근상을 받을 수 있는 출결 기록은 다음 43가지이다.

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

한 학기가 N일일 때, 개근상을 받을 수 있는 출결 기록의 개수를 구하시오.

첫째 줄에 정수 N이 주어진다. N은 1,000 이하이다.

첫째 줄에 개근상을 받을 수 있는 출결 기록의 개수를 1,000,000으로 나눈 나머지를 출력한다.