추진력 수열 찾기

길이가 $n$인 수열 $A=\{a_1, \cdots, a_n\}$이 다음 조건을 모두 만족하면, $A$를 추진력 $f_A$를 가진 추진력 수열이라고 하자.

• $n \ge 3$이다.
• $1 \le i \le n$인 모든 정수 $i$에 대해, $a_i$는 정수이고 $1 \le a_i < 10^9$이다.
• 모든 $1 \le i \le n-2$에 대해 $a_{i+1}=a_i+d$를 만족하는 양의 정수 $d$가 존재한다. 즉, 마지막 항 $a_n$을 제외한 수열 $\{a_1, \cdots, a_{n-1}\}$은 공차가 양의 정수인 등차수열이다.
• $a_n=a_{n-1}\cdot f_A$를 만족하는 $2$ 이상인 정수 $f_A$가 존재한다.

이를테면 $A=\{2, 3, 4, 8\}$은 $d=1$, $f_A=2$일 때 모든 조건을 만족하므로 추진력 수열이다.

추진력 수열 $\{2, 3, 4, 8\}$이 추진력을 얻는 모습

숫자로만 이루어진 문자열 $S$가 주어진다. $S$가 $a_1, \cdots, a_n$을 공백 없이 차례대로 이어 붙인 문자열이 되도록 하는 추진력 수열 $A=\{a_1, \cdots, a_n\}$가 존재하는지 판단하라.

각 $a_i$를 문자열로 쓸 때 앞에 불필요한 0을 붙일 수 없다. 조건을 만족하는 수열이 여러 개라면, $f_A$가 가장 작은 수열을 찾아야 한다.

첫째 줄에 문자열 $S$가 주어진다. $S$의 길이는 $3$ 이상 $2\,348$ 이하이고, 각 문자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중 하나이다.

단, $S$의 첫 번째 문자는 0이 아니다.

$S$에 대해 조건을 만족하는 추진력 수열 $A$가 존재하면, $f_A$를 정수로 출력한다. 가능한 $A$가 여러 개라면 그중 가장 작은 $f_A$를 출력한다.

조건을 만족하는 추진력 수열이 존재하지 않으면 0을 출력한다.