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

유빈이에게는 4×n 크키의 카펫이 하나 있었다.

유빈이는 신하들에게 이 카펫을 3×1 타일과 1×3 타일로 빈틈없이 메우라는 명령을 내렸다.

여러분이 신하들을 도와서 4×n 크기의 카펫을 3×1 타일과 1×3 타일로 메우는 방법의 수를  구하는 프로그램을 작성하시오.

입력 형식

첫째 줄에는 테스트 케이스의 수 T가 주어진다. (1 <= T <= 100)

그 다음 T개의 줄에는 카펫에 가로 길이 N이 주어진다. (세로 길이는 4) (1 <= N <= 10,000)

출력 형식

각 테스트 케이스마다 문제의 정답을 1,000,000,007로 나눈 나머지를 출력한다.

예제 입력

3
3
6
3333

예제 출력

3
13
524313417