Aniruddha loves to code on HackerEarth. There are some type of problems which he likes the most. Problems are tagged with non empty strings containing only 'H' or 'E' or both. But he likes the problems tagged with strings containing no consecutive E's. Given an integer N, find maximum number of problems Aniruddha may like which are tagged with strings of length less than or equal to N.

Input
First line contains single integer, T, the number of test cases. Each of next T lines contains single integer N.

Output
For each test case output single integer, the answer to the problem i.e maximum number of problems Aniruddha may like which are tagged with strings of length less than or equal to N. Output answer modulo 10⁹ + 7 (i.e. 1000000007).

Constraints
1 ≤ T ≤ 10^6
1 ≤ N ≤ 10^6