Finding a Momentum Sequence

Call a sequence $A=\{a_1, \cdots, a_n\}$ of length $n$ a momentum sequence with momentum $f_A$ if it satisfies all of the following conditions.

• $n \ge 3$.
• For every integer $i$ with $1 \le i \le n$, $a_i$ is an integer and $1 \le a_i < 10^9$.
• There exists a positive integer $d$ such that $a_{i+1}=a_i+d$ for every $1 \le i \le n-2$. In other words, after removing the last term $a_n$, the sequence $\{a_1, \cdots, a_{n-1}\}$ is an arithmetic progression with positive integer common difference.
• There exists an integer $f_A \ge 2$ such that $a_n=a_{n-1}\cdot f_A$.

As an illustration, $A=\{2, 3, 4, 8\}$ is a momentum sequence because it satisfies all conditions with $d=1$ and $f_A=2$.

A momentum sequence $\{2, 3, 4, 8\}$ gaining momentum

Given a string $S$ consisting only of digits, determine whether there exists a momentum sequence $A=\{a_1, \cdots, a_n\}$ such that $S$ is exactly the concatenation of $a_1, \cdots, a_n$ with no spaces.

When writing any $a_i$ as a string, leading zeros are not allowed. If more than one valid sequence exists, find one with the smallest possible $f_A$.

The first line contains the string $S$. The length of $S$ is at least $3$ and at most $2\,348$, and every character of $S$ is one of 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9.

The first character of $S$ is never 0.

If there exists a momentum sequence $A$ satisfying the conditions for $S$, print $f_A$ as an integer. If more than one such $A$ exists, print the smallest possible value of $f_A$.

If no such momentum sequence exists, print 0.