접기

문자열에 대한 연산으로 접기(folding)를 정의한다. 접기는 여러 번(0번일 수도 있다) 접는 것으로 이루어진다. 각 접기는 연속한 두 글자 사이에서 일어난다. 문자열의 뒷부분(시작점에서 더 먼 쪽)을 앞부분(시작점에 가까운 쪽) 위에 올려놓는데, 방향은 반대이고 접힌 위치에 맞춰진다. 이 연산을 거치면 구조가 접은 횟수보다 한 층 더 많아진다.

접고 나면 문자열은 여러 개의 글자 더미로 보인다. 같은 더미에 있는 글자가 모두 같으면 그 접기를 유효하다고 한다.

접기의 대응 집합은 접힌 위치 바로 앞에 있는 글자들의 원래 문자열에서의 위치 집합이다. 예를 들어 2번째와 3번째 글자 사이에서 한 번 접는 접기의 대응 집합은 $\{2\}$이고, 한 번도 접지 않는 접기의 대응 집합은 공집합이다. 두 접기는 대응 집합이 같을 때만 같은 것으로 본다.

집합 $S$가 등차이려면 정수 $a$와 $b$($0 \leq b < a$)가 존재하여 $x \in S \iff 1 \leq x < n, x = b \pmod a$를 만족해야 한다. 여기서 $n$은 문자열의 길이다. 예를 들어 $n = 10$이면 $\emptyset$, $\{2\}$, $\{1,9\}$, $\{2, 4, 6, 8\}$은 등차 집합이고, $\{1,2,4\}$, $\{1,5\}$, $\{7,8,9\}$은 등차 집합이 아니다.

유효하고 대응 집합이 등차 집합인 접기를 아름다운 접기라고 한다. 그림은 힌트 부분을 본다.

주어진 문자열에 대해 아름다운 접기의 개수를 구한다.

첫 줄에 문자열이 주어진다. 문자열은 라틴 알파벳, 숫자, 밑줄(_), 하이픈(-)으로 이루어지며 길이는 $n$이다($1 \leq n \leq 10^6$).

아름다운 접기의 개수를 한 줄에 출력한다.

첫 번째 예제에서 아름다운 접기의 대응 집합은 다음과 같다. $\emptyset$, $\{1\}$, $\{2\}$, $\{3\}$, $\{4\}$, $\{1,3\}$, $\{1,4\}$, $\{2,4\}$, $\{1,2,3,4\}$.

문자열 "aabccbaa"의 아름다운 접기이다. 대응 집합은 $\{1,4,7\}$이다.

문자열 "abc"의 아름다운 접기이다. 대응 집합은 $\emptyset$이다.

이 접기는 유효하지 않지만, 대응 집합은 등차 집합이다. 대응 집합은 $\{2,6,10\}$이다.

윗부분이 아랫부분과 같은 방향으로 놓이므로 접기가 아니다.

윗부분은 오른쪽으로 간다고 보면 같은 방향이고, 왼쪽으로 간다고 보면 위치가 맞지 않으므로 접기가 아니다.

이 접기는 유효하지만, 대응 집합은 등차 집합이 아니다. 대응 집합은 $\{4,6\}$이다.