How to solve the following recurrence relation for N ≤10⁹

F(n)=F(n−1)+F(n−2)+F(n−1)∗F(n−2)

(Assuming that we are provided with the values of F(1) and F(2) )

(EDIT: The problem link is attached.)

Here is the link to the problem . I have gone through the editorial but didn't got the approach ( Although I got that we don't need to take more than 2 occurences of a partical triplet [x1,x1+1,x1+2] ) ,I was thinking of DP with three states position i, frequency of i-1^th character we took and frequency of i-2^nd character we took.

But wasn't able to come up with a solution. Can anybody help me with the solution ?

How to approach Constructive Algorithm problems?

Can you share some of the good problems ?