24464번 - 득수 밥 먹이기

문제

프로젝트 하느라 바쁜 득수는 밥 먹을 시간이 부족하다. 그래서 주로 찾는 식당 네 개 중 하나에서 하루에 한 번 밥을 먹는다. 귀찮으면 굶을 때도 있다.

늘 새로운 느낌을 받고 싶었던 득수는 다음과 같은 규칙으로 다음날 갈 식당을 정한다.

• 첫날에는 굶거나, 임의로 원하는 식당 하나를 골라서 간다.
• 어제 굶지 않았다면, 오늘은 식당을 가지 않아도 된다.
• 어제 식당을 가지 않았다면, 오늘은 식당을 가서 밥을 먹어야 한다.
• 오늘 간 식당은 다음날 가지 않는다.
• 오늘 간 식당과 이웃한 식당은 다음날 가지 않는다.

만약 2번 식당을 오늘 갔다면, 다음날 1ドル,ドル 2ドル,ドル 3ドル$번 식당은 가지 않는다. 따라서 새로운 느낌을 받으려면 4ドル$번 식당을 가거나 굶어야 한다.

득수가 $N$일 치 식단표를 만들려고 한다. 위 규칙을 따라 식단표를 만들 때 가능한 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에는 득수가 만들어야 하는 점심 식단의 총 날짜 $N$이 입력으로 들어온다. $(1 \le N \le 200,000円)$

출력

$N$일 치 식단표를 만들 때 가능한 경우의 수를 1ドル,000円,000円,007円(=10^9+7)$로 나눈 나머지를 출력한다.

제한

힌트