题目描述

学校有一条宽 $2$、长 $n$ 的走廊，要用两种地砖把它铺满：

• $1 \times 2$ 的长条砖，可以横着放，也可以竖着放；
• $2 \times 2$ 的方砖。

地砖不能重叠，也不能超出走廊。两种铺法只要有某个位置铺的砖不同，就算作不同的铺法。

总务处想知道不同长度的走廊各有多少种铺法。共有 $T$ 次询问，每次给出一个 $n$，请输出铺满 $2 \times n$ 走廊的方案数。因为答案可能很大，请输出它除以 $10^9+7$ 的余数。

输入格式

第一行一个整数 $T$，表示询问次数。

接下来 $T$ 行，每行一个整数 $n$。

输出格式

输出 $T$ 行，每行一个整数，表示对应的方案数除以 $10^9+7$ 的余数。

样例 #1

样例输入 #1

3
1
3
4

样例输出 #1

1
5
11

样例解释

用 | 表示一块竖放的长条砖，== 表示上下叠着的两块横放长条砖，[] 表示一块方砖：

• $n = 1$：只能竖放一块，$1$ 种；
• $n = 3$：| | |、| ==、== |、| []、[] |，共 $5$ 种。

提示

数据范围

• 对于 $30\%$ 的数据：$T = 1$，$n \le 20$；
• 对于 $60\%$ 的数据：$T = 1$；
• 对于 $100\%$ 的数据：$1 \le T \le 10^5$，$1 \le n \le 10^6$。

提示

• 设 $f_n$ 表示铺满 $2 \times n$ 走廊的方案数。考虑走廊最右边是怎么铺的：要么是一块竖放的长条砖，要么是占满最后两列的「两块横放长条砖」或「一块方砖」。由此可以得到递推式。
• 询问很多，每次都从头递推会超时。可以先把 $f_1 \sim f_{10^6}$ 全部算好存进数组，询问时直接输出。
• 每一步都要取余，计算中间结果时注意 int 可能溢出。