Observation: Turn this into directed graph!
Consider the following case: $\frac a b = v_1$
Do the same thing for $\frac b c = v_2$.
Compute $\frac a c$, isn’t it just $v_1 * v_2$, the traversal path from a to c? There you go!
Matrix fast exponentiation!
Observe that when $n = 2$
$ \begin{bmatrix} 1 & 1 \newline 1 & 0 \newline \end{bmatrix}^{2 - 1} * \begin{bmatrix} f(1) \newline f(0) \newline \end{bmatrix} = \begin{bmatrix} f(0) + f(1) \newline f(1) \newline \end{bmatrix} = \begin{bmatrix} f(2) \newline f(1) \newline \end{bmatrix} $
So in general, we get
$ \begin{bmatrix} 1 & 1 \newline 1 & 0 \newline \end{bmatrix}^{n - 1} * \begin{bmatrix} f(1) \newline f(0) \newline \end{bmatrix} = \begin{bmatrix} f(n) \newline f(n - 1) \newline \end{bmatrix} $
Think reversely! DFS from the nodes that touches the sea, and those that are reachable from both seas -> answer!