Șirul Thue-Morse {T_n} e un șir binar care satisface:

• T₀ = 0
• T_2n = T_n
• T_2n+1 = 1 - T_n

Primii câțiva termeni ai lui {T_n} sunt:
01101001100101101001011001101001....

Fie {A_n} șirul de numere întregi sortate astfel încât reprezentarea lor binară apare ca subșir in {T_n}.
De exemplu, numărul zecimal 18 e scris 10010 în baza 2. 10010 apare în {T_n} (de la T₈ la T₁₂), deci 18 e un termen al șirului {A_n}.
Numărul zecimal 14 e scris 1110 în baza 2. 1110 nu apare deloc în {T_n}, deci 14 nu e un termen al șirului {A_n}.

Primii câțiva termeni ai șirului A_n sunt:

Se poate verifica că A₁₀₀ = 3251 și ca A₁₀₀₀ = 80852364498.

Găsește ultimele 9 cifre ale sumei .