There is a binary tree of (n+1) vertices ( (n) is odd ), with vertices labeled (0,1,\ldots,n). At most one letter can be written on each vertex of the tree, and all vertices initially have nothing written on them. The root of the tree is vertex (0). In the tree, vertex (0) is the parent of vertex (1), while all other vertices have either (2) children or (0) children. Bob is lost in one vertex of the tree and wishes to escape the tree by reaching vertex (0). This is very easy for most people with common sense. However, since Bob is an idiot, he created a new way of traversing the tree; introducing the "Idiot First Search". When Bob is on vertex (v) ((1 \le v \le n)), Bob's movement is determined as follows: If vertex (v) is a leaf, Bob always moves to the parent of (v); otherwise, check the next few conditions. If nothing is written on vertex (v), Bob writes ' L ' on vertex (v) and moves to the left child of (v); If ' L ' is written on vertex (v), Bob overwrites it to ' R ' and moves to the right child of (v); If ' R ' is written on vertex (v), Bob erases it and moves to the parent of (v). It takes exactly (1) second for Bob to move to an adjacent vertex, so Bob will take exactly (x) seconds to perform (x) moves. It has been shown that regardless of which vertex Bob starts on, Bob can reach vertex (0) in a finite (though possibly inexplicably large) amount of time. We don't know who proved it; surely it can't be Bob, but it is definitely proven. For each vertex (k=1,2,\ldots,n), please determine the total time it takes to reach vertex (0) if Bob started on vertex (k), in seconds. As the values may be huge, you are only asked to compute them modulo (10^9+7). Each test contains multiple test cases. The first line contains the number of test cases (t) ((1 \le t \le 10^4)). The description of the test cases follows. The first line of each test