题目描述
lxd今年选的体育课是乒乓球，在这一年里老师一共教了5种基本动作：分别为正手推球，下旋球 ，上旋球，正手攻球和拉弧圈。
考试的规则如下：
老师会给你动作顺序，例如老师考3个动作，顺序为：下旋球->正手攻球->上旋球。
然后比赛会进行三回合，第一回合由老师发球，然后你只能打下旋球，然后由老师接球
第二回合，老师接住你的下旋球，并打给了你，然后你只能正手攻球，然后由老师接球
第三回合，老师接住你的正手攻球，并打给了你，然后你只能打上旋球，完成之后你通过考试。
但是lxd学的并不好，当他第 i 回合为下旋球且第 i+1 回合为上旋球，或当他第 i 回合为拉弧圈且第 i+1 回合为正手攻球时，他将无法接到球而不能通过考试（说到底还是菜）。
在考试之前老师会告诉同学考n回合，但是却没有说动作顺序，心急如焚的lxd想请你帮助他计算对于n回合，一共有多少种顺序lxd是可以通过考试的，结果对1000000007取模。
假设老师神乎其技不可能失误，你除了那两种情况外也不失误（不失误：就是一定会按照考试规则打出相应的球）
输入描述
第一行是一个整数T，表示一共T组测试用例，接下来T行每行一个整数n，表示一共打n回合
输出描述
对于每一个n输出一个整数，表示顺序的种类数
样例输入1
3 2 3 10
样例输出1
23 105 4315343
数据范围
$1<=n,T<=100000 $
无其他限制
