A116098.拆卸爆能器

小W（并非上题那个 小W）要拆卸爆能器，可是这个爆能器被做了手脚，需要输入密码才能拆卸。

有如下两种类型的拼图（如果您看不清可以放大）：

问你用这两种拼图覆盖一个 $2\times n$ 的矩形的方案数，答案对 $10^9+7$ 取模。

拼图可以在此基础上任意旋转，但不能拆卸或斜放，或者超出规定的矩形。

总方案数就是密码，小W 需要你的帮助。

第一行输入一个正整数 $T$ 代表数据组数。

接下来 $T$ 行，每行一个正整数 $n$，含义如题。

本题一个测试点内有多组测试数据。
对于每组测试数据，输出一行一个整数表示总方案数，记得取模 $10^9+7$。

样例解释

对于第 $2$ 组测试数据，以下是五种方案：

数据范围

对于 $100\%$ 的数据，$1\le T \le 10$。

测试点编号	$n\le$
$1\sim 2$	$10^3$
$3\sim 5$	$10^6$
$6\sim 10$	$10^{12}$

温馨提示

样例较强，如果您打的是第一档的暴力可以删除后两组样例；如果您打的是第二档暴力可以删除最后一组样例；如果您通过了样例，那您大概率可以通过此题。