Valid Spell Sequences

In the magical world, wizards cast spells using sequences of magical symbols. Each valid sequence is formed according to specific rules. The number of valid sequences of length (n) is defined by the recurrence:

[ dp(1)=2, \quad dp(2)=4, \quad dp(n)=dp(n-1)+dp(n-2)\quad \text{for } n\ge3, ]

All answers must be computed modulo (10^9+7). Given an integer (n) for each test case, determine the number of valid spell sequences that can be formed. For example, when (n=2), the answer is 4, and when (n=3), the answer is 6.

inputFormat

The input begins with a single integer (T) ((1 \le T \le 10^5)), the number of test cases. Each of the following (T) lines contains one integer (n) ((1 \le n \le 10^6)), representing the length of the spell sequence.

outputFormat

For each test case, output a single integer — the number of valid spell sequences of length (n), computed modulo (10^9+7). Each result should be printed on a new line.## sample

3
1
2
3

2
4
6