4×n Tiling

Time limit2sMemory limit256 MB

Summary

Count the ways to tile a 4 by N board with 1 by 3 and 3 by 1 trominoes modulo 1000000007 for each test case.

Level: Medium6 of 10
Topics: Dynamic programming, Bit manipulation
Solved: No attempts yet

Problem

The kingdom of icpc was once ruled by a very nasty king named Yubin.

Yubin owned a single carpet of size 4×n. He ordered his servants to cover the whole carpet with 3×1 tiles and 1×3 tiles, leaving no gap.

Help the servants and count the ways to cover a 4×n carpet with 3×1 tiles and 1×3 tiles. Tiles must not overlap and must not stick out of the carpet, and you may use as many tiles of each kind as you want.

Input

The first line contains the number of test cases $T$ . ( $1 \le T \le 100$ )

Each of the next $T$ lines contains the width $N$ of the carpet, one per line. The height is always 4. ( $1 \le N \le 10000$ )

Output

For each test case, print the number of ways to cover the carpet modulo $1000000007$ , one per line.

Examples2

Example 1
Input
```
3
3
6
3333
```
Expected output
```
3
13
524313417
```
Example 2
Input
```
2
1
2
```
Expected output
```
0
0
```