eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Задача A + B

Задача A + B

Ліміт часу 4 секунди
Ліміт використання пам'яті 128 MiB

QQ та OO постійно грають у гру A + B. QQ називає два десяткових числа A та B, а OO відразу ж називає їх суму. Проте займатись одним і тим же тривалий час скучно. Тому сьогодні покінчимо з легкою грою, і уведемо у гру нові правила.

Правило1: При додаванні чисел A та B використовуємо двійкове подання чисел A та B.

Правило2: Ми можемо накладати одинаковий суфікс A та префікс B.

Правило3: Якщо двійкове подання числа B є підрядком A, то можемо використовувати A для перекриття B.

Щоб зробити задачу більш цікавою, QQ називає n чисел, а OO повинен використовуючи кожне з них один раз, знайти найменшу можливу суму. У OO немає часу на роздуми і він просить у Вас допомоги.

Вхідні дані

Вхідні дані складаються з декількох тестів. Коженй тест починається числом n, за яким йде n (0 < n < 16) рядків, кожен з яких містить десяткове число a_i (0 < a_i < 2^64) як вказано в умові задачі. Вхідні дані слід опрацьовувати до кінця файлу.

Вихідні дані

Для кожного тесту у окремому рядку необхідно вивести найменшу можливу відповідь. Якщо відповідь велика, то її слід обчислювати по модулю 1000000009.

Приклад

Вхідні дані #1
2
5
3
3
245
351
107
Вихідні дані #1
11
3935