丽江古城的东巴织锦

题目背景

“丽江雪水化千寻，织就东巴七彩云。”

在美丽的云南丽江古城，纳西族的“胖金妹”（纳西语对美丽姑娘的尊称）们擅长一种古老而精美的工艺——东巴织锦。

阿勒秋是古城里手艺最出众的织女。今天，她接到了一份来自远方的特殊订单，需要编织一条极其细长的彩色织锦。为了凸显纳西族的色彩哲学，这条织锦的图案必须遵循严格的传统审美规律。

题目描述

阿勒秋要编织的织锦可以看作是一个 $2$ 行 $W$ 列的网格。 她手头刚好有 $4$ 种不同颜色的天然染料（例如：板蓝根染的蓝、茜草染的红、栀子染的黄、五倍子染的黑）。

为了让织锦的图案具有丰富的层次感，阿勒秋立下了一个规矩：任意两个相邻的网格（上下相邻或左右相邻），必须染成不同的颜色。

由于织锦非常长，阿勒秋想知道，究竟有多少种不同的涂色（编织）方案？ 由于方案数可能极其庞大，请你编写程序帮她计算出涂色方案数对 $1000000007$（即 $10^9+7$）取模后的结果。

输入格式

第一行包含一个正整数 $T$，表示测试数据的组数（即有 $T$ 个不同的订单）。 接下来 $T$ 行，每行包含一个正整数 $W$，表示该条织锦的长度（列数）。

输出格式

输出共 $T$ 行。对于每组测试数据，输出一个整数，表示涂色方案数对 $10^9+7$ 取模的结果。

样例 #1

样例输入 #1

3
1
2
3

样例输出 #1

12
84
588

数据范围与提示

本题采用 Subtask 捆绑测试，时间限制 1.0s。