Definition

The Fibonacci number can be extended non-linearly to a new number called $P(n)P(n)$ with the recurrence relation $\frac{1+P(n+2)}{1+P(n)}=1+P(n+1)\backslash frac\{1+P(n+2)\}\{1+P(n)\}=1+P(n+1)$, for $n\ge 0n\; \backslash geq\; 0$. Find $G(n)=P(n)\mathrm{m}\mathrm{o}\mathrm{d}9G(n)=P(n)\backslash mod\; 9$ if $P(0)=7P(0)=7$ and $P(1)=31P(1)=31$. Brute force will not work!

Constraints

0 <= n <= 10^9

Good luck!