Функция $f$ определена для всех натуральных чисел следующим образом:

\begin{align*} f(1) = 1\\ f(2n) = 2f(n)\\ f(2n+1) = 2n+1 + 2f(n) + \tfrac 1n f(n) \end{align*}

Можно доказать, что $f(n)$ является целочисленным для любого $n$.

Функция $S(n)$ определена как $S(n) = \displaystyle \sum_{i=1}^n f(i) ^2$.

Например, $S(10) = 1530$ и $S(10^2)=4798445$.

Найдите $S(10^{16})$. В качестве ответа приведите остаток от деления полученного результата на $1\,000\,000\,007$.