Chiaki 对一个无穷序列 $a_1, a_2, a_3, \dots$ 感兴趣，该序列定义如下：
$$a_n = \begin{cases} 1 & n = 1, 2 \\ a_{n-1} + a_{n-2} & n \ge 3 \end{cases}$$
Chiaki 想知道该序列前 $n$ 项的和，即 $\sum_{i=1}^{n} a_i$。由于这个数字可能非常大，Chiaki 只对它除以 $(10^9 + 7)$ 的余数感兴趣。
输入格式
输入包含多组测试数据。第一行包含一个整数 $T$ ($1 \le T \le 10^5$)，表示测试数据的组数。对于每组测试数据：
第一行包含一个整数 $n$ ($1 \le n \le 10^{18}$)。
输出格式
对于每组测试数据，输出一个整数表示答案。
样例
输入 1
10 1 2 3 4 5 6 7 8 9 10
输出 1
1 2 4 6 9 13 17 21 26 32