【题目描述】

众所周知，小火星是个爱思考的小朋友，每天都会有很多问题。 这天，他想到了一个很难很难的问题，你能帮他回答这个问题吗？ 小火星会提出 $t$ 个问题，每个问题只有一个整数 $n$，询问有多少个长度为 $n$ 的 01 串满足该 01 串中子串 01、00、10、11 的个数相等，要求答案对 $10^9+7$ 取模。 （注：子串，计算机术语，串中任意个连续的字符组成的子序列称为该串的子串） 请使用较快的输入输出方式以避免超时。

【输入格式】

从文件 seq.in 中读入数据。 第一行一个正整数 $t$，表示数据组数。 接下来 $t$ 行每行一个正整数 $n$，同题意。

【输出格式】

输出到文件 seq.out 中。 每组数据单独一行，表示答案对 $10^9+7$ 取模的结果。

【样例 1 输入】

2
7
9

【样例 1 输出】

0
36

大样例

【数据范围】

• 对于 10% 的数据，$t \le 10$，$n \le 20$；
• 对于另外 10% 的数据，$n$ 一定是 4 的倍数；
• 对于 40% 的数据，$t \le 10$，$n \le 100$；
• 对于 60% 的数据，$t \le 1000$，$n \le 1000$；
• 对于 80% 的数据，$t \le 10^5$，$n \le 10^6$；
• 对于 100% 的数据，$t \le 10^6$，$n \le 10^7$。