Məsələ A + B
QQ və OO daim A + B oyununu oynayırlar. QQ iki onluq ədəd A və B deyir, OO isə dərhal onların cəmini deyir. Lakin uzun müddət eyni şeyi etmək darıxdırıcıdır. Buna görə də bu gün asan oyunu bitirəcəyik və oyuna yeni qaydalar əlavə edəcəyik.
Qayda1: A və B ədədlərini topladıqda, onların ikilik təqdimatından istifadə edirik.
Qayda2: A ilə eyni sonluq və B ilə eyni başlanğıc əlavə edə bilərik.
Qayda3: Əgər B ədədinin ikilik təqdimatı A-nın alt sıradakısa, A-dan B-ni örtmək üçün istifadə edə bilərik.
Məsələni daha maraqlı etmək üçün, QQ n ədəd deyir və OO hər birini bir dəfə istifadə edərək ən kiçik mümkün cəmi tapmalıdır. OO-nun düşünməyə vaxtı yoxdur və sizdən kömək istəyir.
Giriş verilənləri
Giriş məlumatları bir neçə testdən ibarətdir. Hər bir test n ədədi ilə başlayır, ardınca n (0 < n < 16) sıradakı hər biri onluq ədəd a_i (0 < a_i < 2^64) olan sıradakı gəlir. Giriş məlumatları faylın sonuna qədər işlənməlidir.
Çıxış verilənləri
Hər bir test üçün ayrı sırada ən kiçik mümkün cavabı çıxış edin. Əgər cavab böyükdürsə, onu 1000000009 modulu ilə hesablayın.