---

Problem 463

---

Xem đề gốc (tiếng Anh)

Quy tắc truy hồi kỳ lạ

$f(0)=0$, $f(2n-1)=f(n)$, $f(2n)=f(n)+f(n-1)+1$ với $n \ge 1$. Tính $\sum_{n=0}^{10^{15}} f(n) \pmod{10^9}$.

---