Thue-Morse 序列 $\{T_n\}$ 是一个二进制序列，满足：

• $T_0=0$
• $T_{2n}=T_n$
• $T_{2n+1}=1-T_n$

$\{T_n\}$ 的前几项给出如下：
$01101001100101101001011001101001\cdots$

我们将 $\{A_n\}$ 定义为整数的排序序列，以便每个元素的二进制表达式显示为 $\{T_n\}$ 中的子序列。
例如，十进制数$18$用二进制表示为$10010$。 $10010$ 出现在 $\{T_n\}$（$T_8$ 到 $T_{12}$）中，因此 $18$ 是 $\{A_n\}$ 的元素。
十进制数$14$用二进制表示为$1110$。 $1110$ 永远不会出现在 $\{T_n\}$ 中，因此 $14$ 不是 $\{A_n\}$ 的元素。

$\{A_n\}$ 的前几项给出如下：

$n$	$0$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$	$11$	$12$	$\cdots$
$A_n$	$0$	$1$	$2$	$3$	$4$	$5$	$6$	$9$	$10$	$11$	$12$	$13$	$18$	$\cdots$

我们还可以验证 $A_{100}=3251$ 和 $A_{1000}=80852364498$。

查找 $\sum _{k=1}^{18}{A}_{{10}^k}$ 的最后 $9$ 位。