Double or Add Possibilities

After some time, Jack and Jill get bored even of their Multiply or Add game. Jack proposes a new game - he will start with the number 2, then performs i turns as per the rules of the original Double or Add game (without showing Jill) to yield some final number n. Jill must then guess the number n after only being told i.

Formally, the rules of the game are as follows:

• Jack always starts at the number 2.
• Each turn, Jack can perform one of two actions, either
  • Double the current number, or
  • Add 1 to the current number.
• However if he added 1 to the number on the previous turn, then he cannot perform that same action again on the next turn.
• After performing i turns yielding the final number n, Jack tell Jill the value of i.
• Without having witnessed the actions made by Jack, Jill must guess the value of n.

Jill thinks for a moment. The game sounds like it could be fun, but she wonders what the probability is to guess n for any given i...

Problem Statement

Given a number of moves i, calculate u being the total quantity of unique integers which could be yielded after applying the above rules to the starting number 2 for a total of i turns.

The probability to guess n will be equal to 1 / u.

Input Data
First line is Q, the quantity of testcases.
Q lines will then follow, each with a single integer i.

Answer
Should consist of Q space-separated values of u corresponding to each testcase.
Report all values modulo 1000000007

Example

input data:
5
0
1
2
123
999999999

answer:
1 2 3 822117231 999999994