题目描述

经过数年魔法的沉淀，帕秋莉将她那浩瀚无边的魔法的一部分浓缩到了一些特质的珠子中。

由于帕秋莉爱好和平，她只把象征生命和觉醒的木属性魔法和果实和丰收的金属性魔法放入了珠子中。

她认为光要这些珠子没有什么用处，于是她想将这些珠子串成魔法手环，这样就好看多了。于是，她拿出来用来串这些珠子的线 - 雾雨灵径。

她将这些珠子串到一起之后发现了一些性质：只要相邻珠子间的两个珠子中有一个是金属性的，那么它们之间的雾雨灵径的颜色就为金色。

帕秋莉想要一个全都是金色的手环，而且她还想知道一共有多少种方案。由于她还要研究新的魔法，她就把这件事交给了你。由于她的魔法浩瀚无边，她有无穷的珠子。

她并不想看着好几十位的数字，于是你需要对 $1000000007$ 进行取模。

输入格式

输入包含多组数据。

第一行一个正整数 $T$ ，表示数据组数。

之后每组数据有一个 $n$ 代表木属性珠子和金属性珠子的总个数。

输出格式

对于每组数据，输出取模后的方案数。

2
5
20

11
15127

3
9
99
999

76
281781445
445494875

5  
123
1234
12345
123456
1234567

528790589
200102666
537707871
262341000
534036342

提示

这里给出 $n = 5$ 时，样例的解释：

使用 $1, 2, 3, 4, 5$ 来代表各个珠子。

可行的方案是（其中的数字代表染成金元素的珠子序号）：

$\{1, 3, 5\}, \{1, 2, 4\}, \{1, 3, 4\}, \{2, 3, 5\}, \{2, 4, 5\}$

$\{1, 2, 3, 4\}, \{1, 2, 3, 5\}, \{1, 2, 4, 5\}, \{1, 3, 4, 5\}, \{2, 3, 4, 5\}$

$\{1, 2, 3, 4, 5\}$

对于 $20\%$ 的数据，有 $1 \le n \le 10$ ；

对于 $40\%$ 的数据，有 $1 \le n \le 10^2$ ；

对于 $60\%$ 的数据，有 $1\le n \le 10^6$ ；

对于 $90\%$ 的数据，有 $1 \le n \le 10^9$ ；

对于全部的数据，有 $1\le T \le 10, 1\le n \le 10^{18}$。