---

Problem 989

---

Fibonacci Sum

Write $F_n$ for the $n$-th Fibonacci number, with $F_1 = F_2 = 1$ and $F_{n+1} = F_n + F_{n-1}$.

It is known that $F_n$ is very well approximated by $\varphi^n / \sqrt 5$, where $\varphi$, the golden ratio, is the positive root of the equation $x^2 = x+1$.

Let $G(n)$ be the number of distinct integers $0 \leq x < n$ such that $x^2 \equiv x+1 \pmod n$.

You are given $\displaystyle\sum_{n=1}^{10^3}F_nG(n)\equiv 190950976\bmod(10^9+9)$.

Find $\displaystyle\sum_{n=1}^{10^{14}}F_nG(n)$, giving your answer modulo $10^9+9$.

---

斐波那契和

记$F_n$为第$n$个斐波那契数，其中$F_1 = F_2 = 1$，$F_{n+1} = F_n + F_{n-1}$。

众所周知，$F_n$可以很好地用$\varphi^n / \sqrt 5$近似，其中黄金比例$\varphi$是方程$x^2 = x+1$的正根。

记$G(n)$为满足$0 \leq x < n$且$x^2 \equiv x+1 \pmod n$的不同整数$x$的数目。

已知$\displaystyle\sum_{n=1}^{10^3}F_nG(n)\equiv 190950976\bmod(10^9+9)$。

求$\displaystyle\sum_{n=1}^{10^{14}}F_nG(n)$，并对$10^9+9$取余作为你的答案。

---