eolymp
bolt
Try our new interface for solving problems
Problems

A + B Problem

A + B Problem

Time limit 4 seconds
Memory limit 128 MiB

QQ and OO always play the game of A + B. QQ gives two decimal number A and B, and OO answers the sum at once. But to do the same things too often is boring. So, today they are fed up with the easy game, and they come up with new rules of the game.

Rule1: When add A and B we use the binary system string of A and B.

Rule2: We can overlap the same suffix of A and prefix of B.

Rule3: If the binary system string of B is a substring of A we can use A to overlap B.

To make the problem more interesting, QQ gives n numbers, OO should use every one of them and every one once, then give the smallest of the sum. Now OO have no time to do it and need your help. You're a talented programmer you can do it.

Input data

There are several tests, every test begin with n followed with n (0 < n < 16) lines, each line is a decimal number a_i (0 < a_i < 2^64) as described above. Process until EOF.

Output data

For each test you should print the smallest answer per line, maybe the answer is large you should mod 1000000009.

Examples

Input example #1
2
5
3
3
245
351
107
Output example #1
11
3935