吃水果

吃水果

题目描述
A君喜欢吃水果。
现在桌子上有6种水果:苹果,梨子,桃子,香蕉,橘子和柠檬。
A君现在想吃恰好K盘水果。并且还想吃恰好偶数盘的苹果与偶数盘的梨,其他水果则没有特别要求。
现在假定所有水果都有无限盘,你能告诉他,满足他条件的方案有多少种吗?
A君是按顺序一盘一盘吃水果的,因此两种方案不同当且仅当某一步吃的水果不一样。
由于答案可能很大,你只需要回答结果模10^9+7后的值即可;

输入格式
第一行一个整数T表示数据组数。
接下来每组数据仅一行一个整数K,意义见到题目描述。

输出格式
对每组数据输出一行表示答案。

样例

Input

3
1
2
3

Output

4
18
88

30%的数据:T <= 50 , k <= 1000
80%的数据: T <= 5000 , k 1015
100%的数据: 1 <= T <= 2*10^5 , 1 <= k <= 10^18