【问题描述】
给你n个数组成的环，按顺时针由1到n编号（n顺时针下一个方向是1），每个数一开始都是0，现在要你任意选择一些数将其变为1，满足对于任何一个位置的数，至少满足以下一个条件：
1.自身为1。
2.相邻的数都为1。
请你求出有多少种方案。
由于出题人的智商限制，他并不能处理很多位的数据，你需要将答案对1000000007取模。
【输入形式】
第一行输入一个T（T ≤ 105），代表有T组数据。
对于每组数据，输入一个正整数n（1 ≤ n ≤ 106），代表人数。
【输出形式】
对于每组数据，输出一个正整数c，代表答案，答案对1000000007取模。
【样例输入】
3
1
2
3
【样例输出】
1
3
4
【样例说明】
n为1的时候，可行方案有{1}。
n为2的时候，可行方案有{1}，{2}，{1，2}。
n为3的时候，可行方案有{1，2}，{1，3}，{2，3}，{1，2，3}。
*集合内的元素代表变1的数字的编号
*如何取模：
1.(a + b) % p = (a % p + b % p) % p
2.(a - b) % p = ((a % p - b % p )+p) % p
3.(a * b) % p = (a % p * b % p) % p
4.a ^ b % p = ((a % p)^b) % p
【时间与空间限制】
时间限制：1s
空间限制：256MB
| 难度等级： | 0 |
| 总通过次数： | 27 |
| 总提交次数： | 64 |