Tree Cake

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Chef is well known for his delicious cakes with various flavors and shapes. One of his famous cakes is in the shape of a rooted binary tree of height H. The rooted binary tree has a very interesting property  for each non leaf node v, the height of the subtree rooted at the right child of v is exactly 1 more than that of the subtree rooted at the left child of node v. Note that the height of the leaf node of the tree is considered to be one and that of an empty subtree is considered to be zero. You can observe that the above property uniquely determines the rooted tree for a fixed height. So, instead of giving the entire rooted tree, we will just specify its height in the input.
Chef wants to cut his cake into some vertexdisjoint paths such that each node belongs to exactly one path. He wants your help to find out the minimum number of vertexdisjoint paths that cake be cut into.
Let us take an example. The picture below describes the tree of height H = 4. Chef can cut this tree into 2 vertexdisjoint paths. These two paths are shown in green and red colors, respectively. This is the minimum number of paths that Chef can cut the cake into.
Input
The first line of the input contains an integer T denoting the number of test cases. This is followed by the description of the test cases.
The only line of each test case contains a single integer H.
Output
For each test case, output a single integer in a separate line denoting the minimum number of vertex disjoint paths into which cake can be cut. As the answer could be large, output it modulo 10^{9} + 7
Constraints
 1 ≤ T ≤ 10^{4}
 1 ≤ H ≤ 10^{18}
Example
Input: 2 1 4 Output: 1 2
Explanation
Example case 1. The rooted tree will consist of only 1 node. So, Chef can cut the entire cake into 1 vertexdisjoint path consisting of the single node itself.
Example case 2. This case is already explained in the problem description.
Author:  kingofnumbers 
Tags  kingofnumbers 
Date Added:  3042016 
Time Limit:  3 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.4, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 