문제1776--바둑돌 채우기

1776: 바둑돌 채우기

실행시간 제한: 1 Sec  메모리사용 제한: 128 MB
제출: 195  통과: 67
[제출] [채점기록] [묻고답하기]

문제 설명

1 × 1 크기의 상자가 일렬로 N 개 늘어져 있다.

이 상자에 바둑돌을 집어넣으려고 하는데 바둑돌은 한 상자에 하나씩 집어넣을수 있고 또한 바둑돌이 들어있는 상자는 3개 이상 연속 되어서는 안된다. (즉 바둑돌이 들어있는 상자는 최대 2개까지만 붙어있을 수 있다. ) 상자의 수 N 이 주어졌을 때 바둑돌을 넣을 수 있는 경우의 수가 몇 가지나 되는지 알아내는 프로그램을 작성하라.
바둑돌을 하나도 놓지 않는 경우도 한 가지의 경우라고 가정한다.

입력 설명

맨 처음 테스트 케이스의 수 T 가 입력된다. ( 1 ≤ T ≤ 100 )

그 다음 T 만큼 상자의 수 N 이 입력된다. ( 1 ≤ N ≤ 1, 000 )

출력 설명

상자에 바둑돌을 넣을 수 있는 경우의 수를 한 줄로 출력한다. 만약 정답이 1, 000, 000, 007보다 클 경우 1, 000, 000, 007로 나눈 나머지를 출력한다.

입력 예시 Copy

2
2
3

출력 예시 Copy

4
7

도움

 

두번째 케이스의 경우 1 × 3의 상자들에 바둑돌을 채우는 경우는 다음과 같다.
바둑돌이 들어있는 상자를 ● , 들어있지 않은 상자를 ○ 라고 하면
{ ○,○,○ }, { ●,○,○ }, { ○,●,○ }, { ○,○,● }, { ●,●,○ }, { ○,●,● }, { ●,○,● }
로 총 7가지이다.
{ ●,●,● }은 바둑돌이 3개 연속되었으므로 경우의 수에 넣지 않는다.