투에-모스(Thue-Morse) 수열 {T_n}은 아래 조건을 만족하는 이진 수열입니다:

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

{T_n}의 처음 몇 항은 다음과 같습니다:
01101001100101101001011001101001....

{A_n}을 각 원소의 이진 표현이 {T_n}의 부분 수열로 나타나는 정수들의 정렬된 수열로 정의합니다.
예를 들어, 십진수 18 은 이진수로 10010 입니다. 10010 은 {T_n} (T₈에서 T₁₂까지)에 나타나므로, 18 은 {A_n}의 원소가 됩니다.
반면에 십진수 14 는 이진수로 1110 인데 1110 은 {T_n}에 결코 나타나지 않기 때문에, 14 는 {A_n}의 원소가 될 수 없습니다.

A_n의 처음 몇 항은 다음과 같습니다:

또한 A₁₀₀ = 3251 이고 A₁₀₀₀ = 80852364498 입니다.

$\sum \limits_{k = 1}^{18} {A_{10^k}}$ 의 마지막 9 자리 수를 구하세요.