PROGRAMMING:Boiling sheep
Bear_ There are many sheep in Qingqing grassland. These sheep are divided into two kinds. One is hot tempered sheep, the other is gentle tempered lazy sheep_ I want to choose from my own sheep to form a line, now bear_ 2. I want to know how many kinds of legal sequences can be formed if three consecutive boiling sheep cannot be adjacent. Can you tell him how many kinds of legal sequences can be formed（ Suppose bear_ 2. There are infinitely many sheep. The answer may exceed the range of long long. Please take a model of 1000000007 for the answer and output it.)
###Input format:
In the first line, enter the number of sample groups t.
After that, there are t rows, and each row is entered with a positive integer n ($$1 < = n < = 10 ^ 5 $$).
###Output format:
For each positive integer n, output the result after modulus.
###Input example:
```in
two
one
three
```
###Output example:
```out
two
seven
```
###Tips:
20% data, $$1 < = n < = 10$$
40% of data, $$1 < = n < = 20$$
60% of the data, $$1 < = n < = 10 ^ 3$$
100% data, $$1 < = n < = 10 ^ 5$$
answer：If there is no answer, please comment
###Input format:
In the first line, enter the number of sample groups t.
After that, there are t rows, and each row is entered with a positive integer n ($$1 < = n < = 10 ^ 5 $$).
###Output format:
For each positive integer n, output the result after modulus.
###Input example:
```in
two
one
three
```
###Output example:
```out
two
seven
```
###Tips:
20% data, $$1 < = n < = 10$$
40% of data, $$1 < = n < = 20$$
60% of the data, $$1 < = n < = 10 ^ 3$$
100% data, $$1 < = n < = 10 ^ 5$$
answer：If there is no answer, please comment