Binary Products
You have a sequence consisting of n ones. Your task is to explore all possible ways to insert one or more multiplication signs between these ones, ensuring that the resulting expression is valid. This means that multiplication signs cannot be placed consecutively, nor can they appear at the start or end of the sequence. For instance, when n = 4, there are 7 valid expressions: 1×111, 11×11, 111×1, 1×1×11, 1×11×1, 11×1×1, and 1×1×1×1.
Next, compute the sum of the products of these expressions, interpreting the numbers in binary format: 1_2×111_2 + 11_2×11_2 + 111_2×1_2 + 1_2×1_2×11_2 + 1_2×11_2×1_2 + 11_2×1_2×1_2 + 1_2×1_2×1_2×1_2 = 33.
Your goal is to determine this sum for any given n.
Input
The first line contains T (1 ≤ T ≤ 1000) — the number of test cases. Each of the following T lines contains a single integer n (2 ≤ n ≤ 10^9).
Output
For each test case, output the calculated sum modulo 1000000007.