QQ и OO постоянно играют в игру \textbf{A + B}. QQ называет два десятичных числа \textbf{A} и \textbf{B}, а OO сразу же называет их сумму. Однако заниматься одним и тем же долгое время скучно. Поэтому сегодня покончим с легкой игрой, и введем в игру новые правила. \textit{Правило1:} При сложении чисел \textbf{A} и \textbf{B} используем двоичное представление чисел \textbf{A} и \textbf{B}. \textit{Правило2:} Мы можем накладывать одинаковый суффикс \textbf{A} и префикс \textbf{B}. \textit{Правило3:} Если двоичное представление числа \textbf{B} является подстрокой \textbf{A}, то можем использовать \textbf{A} для перекрытия \textbf{B}. \includegraphics{https://static.e-olymp.com/content/88/88dbad66804ca2d02bf7827b49f02f1253ec77ec.jpg} Чтобы сделать задачу более интересной, QQ называет \textbf{n} чисел, а OO должен используя каждое из них один раз, найти наименьшую возможную сумму. У OO нет времени думать и он просит у Вас помощи. \InputFile Входные данные состоят из нескольких тестов. Каждый тест начинается числом \textbf{n}, за которым следует \textbf{n} (\textbf{0} < \textbf{n} < \textbf{16}) строк, каждая из которых содержит десятичное число \textbf{a_i} (\textbf{0} < \textbf{a_i} < \textbf{2^64}) как указано в условии задачи. Входные данные следует обрабатывать до конца файла. \OutputFile Для каждого теста в отдельной строке следует вывести наименьший возможный ответ. Если ответ большой, то его следует вычислять по модулю \textbf{1000000009}.