Рассмотрим бесконечную последовательность S, начинающуюся так:
S = 1, 1, 2, 1, 3, 2, 4, 1, 5, 3, 6, 2, 7, 8, 4, 9, 1, 10, 11, 5, ...

Выделим для каждого целого числа его первое появление в последовательности:
S = 1, 1, 2, 1, 3, 2, 4, 1, 5, 3, 6, 2, 7, 8, 4, 9, 1, 10, 11, 5, ...

Этой последовательности характерны следующие свойства:

• Выделенные числа - последовательные целые числа, начиная с 1.
• Непосредественно перед каждым невыделенным числом a_i находится ровно └√a_i┘ прилегающих выделенных чисел, где └ ┘ - функция пол.
• Если убрать все выделенные числа из последовательности, оставшиеся в ней числа сформируют последовательность, идентичную S. Таким образом, S - это фрактальная последовательность.

Пусть T(n) будет суммой первых n элементов этой последовательности.
Известно, что T(1) = 1, T(20) = 86, T(10³) = 364089 и T(10⁹) = 498676527978348241.

Найдите T(10¹⁸). В качестве ответа приведите последние 9 цифр полученного числа.