Задача A + B
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.