---

Problem 709

---

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

Even Stevens

$f$ là hàm đệ quy: $f(n) = n$ nếu $n \le 2$; $f(n) = f(n-1) + f(\lfloor n/2 \rfloor)$ nếu $n$ lẻ; $f(n) = f(n/2) + f(n-1)$ nếu $n$ chẵn. Tính $f(2^{30}) \pmod{10^9}$.

---