Consider the infinite integer sequence S starting with:
$S=1,1,2,1,3,2,4,1,5,3,6,2,7,8,4,9,1,10,11,5,\dots$

Circle the first occurrence of each integer.
$S=\overline{)1},1,\overline{)2},1,\overline{)3},2,\overline{)4},1,\overline{)5},3,\overline{)6},2,\overline{)7},\overline{)8},4,\overline{)9},1,\overline{)10},\overline{)11},5,\dots$

The sequence is characterized by the following properties:

• The circled numbers are consecutive integers starting with $1$.
• Immediately preceding each non-circled numbers $a_i$, there are exactly $\lfloor \sqrt{a_i}\rfloor$ adjacent circled numbers, where $\lfloor \rfloor$ is the floor function.
• If we remove all circled numbers, the remaining numbers form a sequence identical to $S$, so $S$ is a fractal sequence.

Let $T(n)$ be the sum of the first $n$ elements of the sequence.
You are given $T(1)=1$, $T(20)=86$, $T({10}^3)=364089$ and $T({10}^9)=498676527978348241$.

Find $T({10}^{18})$. Give the last $9$ digits of your answer.