Alice’s bedroom has N tiles in a row and She wants to colour them using Red and Blue colour. So, there can be 2^N patterns that she can get using these 2 colours. Out of those patterns, She doesn’t like those patterns in which any Four consecutive tiles are coloured red. You need to tell the number of different patterns that can be formed that Alice likes.

Note that each tile can be either coloured with a Red colour or a Blue colour.

INPUT:

First line contains T, the number of test cases.

Next T lines contain a single integer denoting N.

OUTPUT:

For each test case, Print the answer in a new line. Since the answer can be large, print it modulo 1000000007.

CONSTRAINTS:

1 <= T <= 10⁵

1 <= N <= 10⁶