DMOPC '19 Contest 1 P6 - Bob and Binary Strings

View as PDF

Submit solution

Points: 25 (partial)
Time limit: 1.4s
Memory limit: 512M

Problem types

Bob is playing with binary strings. He defines two strings S and T to be similar if at least one of the following conditions holds:

  1. S = T
  2. The lengths of both S and T must be divisible by 2. Let S_1 denote the first half of S, and S_2 denote the second half. Similarly, define T_1 and T_2 as the first and second halves of T. Then S and T are similar if either:
    • S_1 is similar to T_1 and S_2 is similar to T_2 or
    • S_1 is similar to T_2 and S_2 is similar to T_1

If both conditions do not hold then S and T are not similar.

Bob begins to wonder about N particular lengths of binary strings. These lengths are a_1,a_2\dots,a_N.

For each a_i, Bob generates all 2^{a_i} possible binary strings of length a_i. He wonders how many ordered pairs of binary strings from his set are similar. Since these numbers may be massive, print the answers modulo 10^9+7.


In all subtasks,
1 \le N \le 50
1 \le a_i \le 10^{18}

Subtask 1 [5%]

1 \le a_i \le 5

Subtask 2 [10%]

All the a_i are odd integers.

Subtask 3 [15%]

1 \le a_i \le 26

Subtask 4 [10%]

1 \le a_i \le 52

Subtask 5 [30%]

1 \le a_i \le 1024

Subtask 6 [30%]

1 \le a_i \le 10^{18}

Input Specification

The first line contains a single integer, N.
N lines follow, the i-th of which containing a single integer, a_i.

Output Specification

Output N lines, the i-th of which containing the answer modulo 10^9+7 for binary strings of length a_i

Sample Input


Sample Output


Sample Input 2


Sample Output 2


Explanation for Sample Input 2

There are a total of 8 ordered pairs of similar strings for binary strings of length 3, and there are a total of 54 ordered pairs of similar strings for binary strings of length 4.


There are no comments at the moment.