---

Problem 759

---

A squared recurrence relation

The function $f$ is defined for all positive integers as follows:
$$f(1)=1$$
$$f(2n)=2f(n)$$
$$f(2n+1)=2n+1+2f(n)+\frac{1}{n}f(n)$$
It can be proven that $f(n)$ is integer for all values of $n$.

The function $S(n)$ is defined as $S(n)={\displaystyle \sum _{i=1}^{n}f(i{)}^2}$.

For example, $S(10)=1530$ and $S({10}^2)=4798445$.

Find $S({10}^{16})$. Give your answer modulo $1000000007$.

---

递推数列的平方和

定义在正整数上的函数$f$满足以下递推关系：
$$f(1)=1$$
$$f(2n)=2f(n)$$
$$f(2n+1)=2n+1+2f(n)+\frac{1}{n}f(n)$$
可以证明，对于任意$n$，$f(n)$的取值均为整数。

再定义函数$S(n)$为$S(n)={\displaystyle \sum _{i=1}^{n}f(i{)}^2}$。

例如，$S(10)=1530$，$S({10}^2)=4798445$。

求$S({10}^{16})$，并将你的答案对$1000000007$取余。

---