题目描述

求有多少个长度为 $n$ 的 01 串满足该串中子串 01，00，10，11 的个数相同。

输入格式

第一行一个整数 $T$，表示数据组数。

接下来每一行一个正整数 $n$。

输出格式

共 $T$ 行，每一行一个答案。输出对 $10^9+7$ 取模。

样例 #1

样例输入 #1

2
7
9

样例输出 #1

0
36

提示

特殊性质 $A$：保证 $n=4k,k\in\mathbb{Z}$。