T425230 「YAC Round 4」爱丽丝送给魔理沙的手链

 > 不可思议之国的爱丽丝

爱丽丝想要自己做一个宝石手链送给魔理沙。爱丽丝用了很多很多大小一样的蓝色宝石和金色宝石作为制作手链的材料，金色代表着魔理沙，蓝色则代表着自己。 宝石手链是 **环状** 的，而且爱丽丝有一个小小的要求：手链中 **每两个相邻的宝石** 中，**至少有一个是蓝色的**。因为爱丽丝觉得只有这样，才能表达自己的心意。 现在，爱丽丝有无穷多个金色和蓝色的宝石，她需要制作一个长度为 $n$ 的宝石手链。 请求出爱丽丝制作出符合她自己要求的宝石手链的方案数。 方案数可能很大，答案对 $10^9 + 7$ 进行取模。

**包含多组测试数据** 第一行输入一个正整数 $T$ ，表示数据组数。 对于每组数据，有一个 $n$ 代表需要制作宝石手链的长度。

对于每组数据，输出一行一个数，表示取模后的制作符合要求手链的方案数。

#### 样例解释 假设蓝色宝石为 $b$,金色宝石为 $g$。 例如第一组样例中，$n = 4$ 时，符合条件的方案有 $bbbb$、$bbbg$、$bbgb$、$bgbb$、$bgbg$、$gbbb$、$gbgb$ 。则答案为 $7$ 种。 #### 数据范围 对于 $20\%$ 的数据，有 $1 \le n \le 10$ ； 对于 $60\%$ 的数据，有 $1\le n \le 10^6$ ； 对于全部的数据，有 $1\le T \le 10, 1\le n \le 10^{18}$ 。