개근상

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

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

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

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

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

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

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

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