4×n 타일링

icpc 왕국에는 아주 못된 왕 유빈이가 있었다.

유빈이에게는 4×n 크기의 카펫이 하나 있었다. 유빈이는 신하들에게 이 카펫을 3×1 타일과 1×3 타일로 빈틈없이 메우라는 명령을 내렸다.

신하들을 도와 4×n 크기의 카펫을 3×1 타일과 1×3 타일로 메우는 방법의 수를 구하는 프로그램을 작성하시오. 타일끼리 겹치거나 카펫 밖으로 나가서는 안 되고, 두 종류 모두 원하는 만큼 쓸 수 있다.

첫째 줄에 테스트 케이스의 수 $T$가 주어진다. ($1 \le T \le 100$)

다음 $T$개의 줄에 카펫의 가로 길이 $N$이 한 줄에 하나씩 주어진다. 세로 길이는 항상 4이다. ($1 \le N \le 10000$)

각 테스트 케이스마다 카펫을 메우는 방법의 수를 $1000000007$로 나눈 나머지를 한 줄에 하나씩 출력한다.