Valid Fibonacci-Like Sequence

You are given a string consisting of digits. Your task is to determine whether the string can be split into a Fibonacci-like sequence. A Fibonacci-like sequence is defined as a sequence of numbers that has at least three elements, and every number (starting from the third) is the sum of the two preceding numbers. When splitting the string into numbers, each number should be non-negative and must not contain leading zeros (except for the number zero itself).

For example, the string "112358" can be split as [1, 1, 2, 3, 5, 8] which forms a valid Fibonacci sequence, while "123456" cannot form such a sequence.

Your program should read the input from stdin and output the result to stdout as either True or False based on whether a valid Fibonacci-like sequence can be formed.

inputFormat

The input consists of a single line containing a string s which is composed only of digits.

For example:

112358

outputFormat

Output a single line: True if the string can be split to form a valid Fibonacci-like sequence, or False otherwise.

For example:

True

## sample

112358

True

</p>