Fibonacci-like Cyclic Number

Consider a decimal number with n digits, \(N = d_1d_2d_3\dots d_n\). A Fibonacci-like sequence \(S\) associated with \(N\) is defined as follows:

• The first \(n\) numbers are \(S_1=d_1, S_2=d_2, \dots, S_n=d_n\).
• For every \(k > n\), \(S_k = \displaystyle\sum_{i=k-n}^{k-1} S_i\). In other words, each term is the sum of the previous \(n\) terms.

If \(N\) appears in its associated sequence \(S\), then \(N\) is called a Fibonacci-like cyclic number. For example, for \(N=197\) (with digits \(1,9,7\)), the sequence is

[ S = {1,\ 9,\ 7,\ 17,\ 33,\ 57,\ 107,\ 197, \dots} ]

and since (197) appears in (S), it is a Fibonacci-like cyclic number.

The problem is: among all numbers between 0 and \(10^7\), find the largest Fibonacci-like cyclic number. This is a result-fill problem; you only need to output the correct integer result. When submitting your answer, output only the integer without any extra characters.

inputFormat

This is a result-fill problem, so there is no input.

outputFormat

Output a single integer, which is the largest Fibonacci-like cyclic number between 0 and \(10^7\).

sample

N/A

197