Alook was composing magical spells for his mage master. The mage was good at spellcasting but since spell design requires intricate mathematics, this task was given to Alook who had the gift of numbers.

The power contained in a spell is a function of its lexicographical structure, which is why Alook wants to extensively test spells of difference lexicographical structures. Spells are composed of 2 types of lexemes : long and short; a short lexeme is one phoneme long while a long lexeme is two phonemes long. A third special type of lexeme of length 2 phonemes can be used only at the beginning of a spell.

Additionally, each phoneme can be uttered in two ways :in a 'high' or a 'low' note. There are still, however only 2 types of lexemes and not 6 as lexemes are characterized only on the basis of their length and not their constituent phonemes. Phonemes are spoken while lexemes are written. Lexemes enforce a substructure on phonemes, but phonemes do not enforce any structure on lexemes.

Every day, Alook writes down spells of all possible lexicographical structures, upto n phonemes in length. His master utters all possible phonetic variations of every written spell to service his oral fixation. Given n, you have to tell how many phonetically different spells the mage casts.

Read about lexeme here : Lexeme
Read abour phoneme here : Phoneme

[Input]
First line contains and integer t denoting number of test cases. Each test consists of single line containing integer n denoting length.

[Output]
For each test case output single line denoting ans.

NOTE: As ans can be large output the ans by taking mod with 10^9 + 7.

[Constraints]
1<=t<=100 1<=n<=1000000000