Последовательность корневых деревьев $T_n$ построена таким образом, что $T_n$ имеет $n$ узлов, пронумерованных от $1$ до $n$.

Последовательность начинается с дерева $T_1$, чьим единственным узлом является его корень под номером $1$.

Для $n > 1$, $T_n$ строится из $T_{n-1}$ следуя приведенной ниже процедуре:

1. Проложить путь от корня $T_{n-1}$ до листа, следуя на каждом узле ветвления к вершине с наибольшим номером.
2. Удалить все ребра на проложенном пути, отсоединяя все узлы на пути от их родительских вершин.
3. Присоединить все осиротевшие узлы к новому узлу под номером $n$, который становится корнем $T_n$.

Например, иллюстрация ниже изображает $T_6$ и $T_7$. Путь, проложенный через $T_6$ для построения $T_7$, отмечен красным.

Пусть $f(n, k)$ будет суммой номеров узлов на пути, соединяющем корень $T_n$ с узлом $k$, включая корень и узел $k$. Например, $f(6, 1) = 6 + 5 + 1 = 12$ и $f(10, 3) = 29$.

Найдите $f(10^{17}, 9^{17})$.