Solution to recurrence

Question

Can anyone tell me how to solve this recurrence efficiently $F(n) = F(n-1) + F(n-2) + F(n-1)*F(n-2)$. I will be provided value of $F(0)$ and $F(1)$ and have to calculate $F(n)$.

$0 \le N \le 10^9$

Answer 1

HINT$$F_{n}+1=G_{n} \implies G_{n}=1+F_{n-1}+F_{n-2}+F_{n-1}F_{n-2}=G_{n-1}G_{n-2}$$ From our given condition. So we have that $$\log G_{n}=\log G_{n-1}+\log G_{n-2}$$