The Thue-Morse sequence {T_n} is a binary sequence satisfying:

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

The first several terms of {T_n} are given as follows:
01101001100101101001011001101001....

We define {A_n} as the sorted sequence of integers such that the binary expression of each element appears as a subsequence in {T_n}.
For example, the decimal number 18 is expressed as 10010 in binary. 10010 appears in {T_n} (T₈ to T₁₂), so 18 is an element of {A_n}.
The decimal number 14 is expressed as 1110 in binary. 1110 never appears in {T_n}, so 14 is not an element of {A_n}.

The first several terms of A_n are given as follows:

We can also verify that A₁₀₀ = 3251 and A₁₀₀₀ = 80852364498.

Find the last 9 digits of .