Problem Description

For an $n$-digit decimal number $N = d_1d_2d_3\dots d_n$, we can generate a quasi-Fibonacci sequence $S$. The first $n$ terms of $S$ are $\{S_1=d_1,S_2=d_2,S_3=d_3,\dots,S_n=d_n\}$. The $k$-th term of $S$ for $k(k>n)$ is $\sum^{k−1}_{i=k−n} S_i$. If the number $N$ appears in the corresponding quasi-Fibonacci sequence $S$, then $N$ is a quasi-Fibonacci cyclic number.

For example, for $197$, the corresponding sequence $S$ is $\{1, 9, 7, 17, 33, 57, 107, 197, \dots \}$. Since $197$ appears in $S$, $197$ is a quasi-Fibonacci cyclic number.

In the range from $0$ to $10^7$, what is the largest quasi-Fibonacci cyclic number?

This is a fill-in-the-blank question. You only need to compute the result and submit it. The result of this problem is an integer. When submitting the answer, output only this integer. Any extra content will cause you to receive no score.

Input Format

There is no input for this problem.

Output Format

Output one integer per line, representing the answer you computed.

Hint

Translated by ChatGPT 5