Consider the fact that for any sequence $G$ with the form of fibonacci, that is: $G_{i+1} = G_i + G_{i-1}$, then $G_i = G_1 \cdot F_i + G_0 \cdot F_{i-1]$. So the problem became to solve two linear equations in integers. Prove it with induction or consider the matrix exponentiation for fibonacci.

You should use Python to avoid overflow (long long isn't sufficient, at least for my implementation). Good Luck!