759 : 漸化式の2乗

関数$f$をあらゆる正の整数に対して次のように定義する： $f(1) = 1$ $f(2n) = 2f(n)$ $f(2n+1) = 2n + 1 + 2f(n) + \frac{1}{n}f(n)$

$f(n)$があらゆる$n$に関して整数であることが証明できる。

関数$S(n)$を$\displaystyle S(n) = \sum_{i=1}^n f(i)^2$と定義する。 例えば、$S(10) = 1530, S(10^2) = 4798445$である。

$S(10^{16})$を求めよ。答えは$1\,000\,000\,007$で割った余りを入力せよ。