A + B Problem#1758
QQ and OO always play the game of A + B. QQ gives two decimal numbers A and B, and OO answers their sum at once. However, doing the same thing for a long time is boring. So today, they are ending the easy game and introducing new rules.
Rule 1: When adding A and B, we use their binary representations.
Rule 2: We can overlap the same suffix of A and the prefix of B.
Rule 3: If the binary representation of B is a substring of A, we can use A to overlap B.
To make the problem more interesting, QQ gives numbers. OO must use every number exactly once and find the smallest possible sum. OO has no time to think and asks for your help.
There are several tests. Each test begins with a number , followed by (0 < n < 16) lines. Each line contains a decimal number a_i (0 < a_i < 2^{64}) as described above. Process the input until the end of file.
For each test, print the smallest possible answer on a separate line. If the answer is large, output it modulo .
Example 1