## DMOPC '19 Contest 1 P6 - Bob and Binary Strings

View as PDF

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

Author:
Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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

1. 2. The lengths of both and must be divisible by . Let denote the first half of , and denote the second half. Similarly, define and as the first and second halves of . Then and are similar if either:
• is similar to and is similar to or
• is similar to and is similar to If both conditions do not hold then and are not similar.

Bob begins to wonder about particular lengths of binary strings. These lengths are .

For each , Bob generates all possible binary strings of length . He wonders how many ordered pairs of binary strings from his set are similar. Since these numbers may be massive, print the answers modulo .

#### Constraints   All the are odd integers.      #### Input Specification

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

#### Output Specification

Output lines, the -th of which containing the answer modulo for binary strings of length #### Sample Input

1
2

#### Sample Output

6

#### Sample Input 2

2
3
4

#### Sample Output 2

8
54

#### Explanation for Sample Input 2

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