该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

求有多少个长度为 $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}$。