6. Obedové menu: ryža

V Číne majú veľa malých chlapcov a dievčat. Chlapcov trochu viac. A ešte viac ryže.

V poslednom čase je ale v ich škôlkach stále viac a viac plačúcich a nešťastných detí. Začali sa totiž učiť matematiku. Konkrétne, zatiaľ sa naučili počítať do veľkých čísel a tiež násobiť a deliť dvomi.

Mohli by ste si myslieť, že majú množstvo domácich úloh, alebo že ich matematika nebaví. Opak je však pravdou. Akonáhle získali túto novú superschopnosť, využívajú ju každý deň. Hlavne pri obede. Skôr než sa pustia do jedenia, každý si spočíta svoje zrnká ryže.¹

Keď má každý spočítanú svoju ryžu, začne sa druhá fáza obeda. Porovnávanie. Ak niekto zistí, že má dvakrát viac zrniek ako spoluškôlkar, má právo povyšovať sa a vysmievať sa mu. Potom nasleduje plač, alebo si ublížený chlapec či dievča nájde niekoho, kto má ešte dvakrát menej ryže. Deti niekedy bývajú kruté.

Pani vychovávateľky sú bezradné. Toľko plaču a kreatívnych nadávok, koľko počuli za posledné obdobie ešte nikdy nezažili. Proces výučby sa samozrejme rýchlo zastavil, no nedá sa deti odnaučiť od toho, čo už vedia.

Preto by, ako náhradné riešenie, chceli niektorým deťom zobrať ryžu a dať im tofu. Ryžu treba zobrať deťom tak, aby nemali žiadni dvaja škôlkari \(x\) a \(2x\) zrniek ryže. Pani vychovávateľky si uvedomujú, že tofu nemá nikto rád², a preto by ho chceli dať čo najmenej deťom. Tiež by ich zaujímalo, koľkými spôsobmi sa dá deťom zobrať najmenší počet ryžových tanierov a rozdať tofu.

Úloha

Na obed je pripravených \(n\) porcií ryže. O každej porcii sa dozviete jedno číslo – počet zrniek ryže. Tieto čísla sú na vstupe usporiadané vzostupne. Niektoré porcie potrebujete odobrať tak, aby nikto nedostal dvakrát viac ryže ako hocikto iný. Inak povedané, aby nezostali žiadne dve porcie, ktoré majú \(x\) a \(2x\) zrniek. Snažíte sa odobrať čo najmenej porcií.

Zistite tiež, koľkými spôsobmi sa dajú porcie odobrať tak, aby boli splnené predošlé požiadavky. Dva spôsoby sú rôzne ak existuje aspoň jedna porcia, ktorú sme v jednom spôsobe nechali a v druhom nie. Keďže týchto spôsobov môže byť veľmi veľa, vypíšte len zvyšok po delení prvočíslom \(1\,000\,000\,009\).

Formát vstupu

Na prvom riadku vstupu je kladné celé číslo \(n\) neprevyšujúce \(1\,000\,000\) udávajúce počet porcií. Na ďalšom riadku nasleduje \(n\) čísel \(r_i\) oddelených medzerami, pričom pre každé z nich platí \(0 < r_i < 10^{18}\). Čísla \(r_i\) sú zoradené od najmenšieho po najväčšie.

Formát výstupu

Vypíšte dve celé čísla oddelené medzerou: najväčší možný počet porcií, ktoré zostanú po odobratí potrebných tanierov a počet spôsobov ich výberov premodulovaný \(1\,000\,000\,009\). Výstup ukončite znakom nového riadku.

Príklad

Input:

8
1 2 2 3 4 5 5 6

Output:

5 4

Žiadne povyšovanie a čo najmenej tofu dosiahneme ak necháme deťom tieto porcie: 1 3 4 5 5, 1 4 5 5 6, 2 2 3 5 5, 2 2 5 5 6