Game of RUN

Game of RUN은 Game of Go(바둑)와 비슷하지만 2차원의 정사각형 격자 대신에 1차원 격자를 사용하는 2인용 게임이다.

Game of RUN의 규칙은 다음과 같다.

• 두 플레이어가 번갈아서 흑돌 또는 백돌을 격자 위에 원하는 만큼 놓는다. $0$개를 놓는 것도 허용된다.
• 한 가지 색깔의 돌이 1칸 이상의 연속한 구간을 차지할 때 그 구간 전체를 그룹이라고 하자. 흑돌 3개가 연달아 놓여 있다면 그 중 흑돌 2개나 1개만을 포함하는 구간은 그룹이 아니다. 이때, 모든 그룹은 적어도 하나의 빈 칸과 이웃하고 있어야 한다. 예를 들어, 아래와 같은 경우들은 각각 흑돌의 그룹과 백돌의 그룹이 빈 칸과 이웃하고 있지 않으므로 올바른 게임 상태가 아니다.

길이 $n$인 게임판에서 가능한 모든 서로 다른 게임 상태의 수를 $1 000 000 007$로 나눈 나머지를 구하시오.

첫 번째 줄에 테스트 케이스의 개수 $T$가 주어진다.

그다음 $T$줄에 걸쳐서 정수 $n$의 값이 한 줄에 하나씩 주어진다.

각 테스트 케이스에 대해 문제의 정답을 한 줄에 출력한다.

• $1\le T\le 10 000$
• $1\le n\le 1 000 000$