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