#1776 바둑돌 채우기

52  1 s   128 MB  

Description

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

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

Input

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

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

Output

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

Sample Input

Sample Output

2
2
3
4
7

HINT

 

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

Source

2011 Ajou University Programming Contest, Division 2