3828：A + B problem

QQ and OO always play the game of A + B. QQ gives tow 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.

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

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