题目描述
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