Farmer John에게는 소들에게 숨기고 싶은 비밀 메시지가 있다. 길이가 최소 2이며 문자 A..Z만 포함하는 문자열이다.

메시지를 암호화하기 위해 FJ는 일련의 “연산”을 적용한다. 문자열 $S$에 대한 연산은 먼저 첫 문자 또는 마지막 문자를 제거해 $S$를 짧게 만든 뒤, 원래 문자열 $S$를 앞이나 뒤에 붙인다. 예를 들어 ABCD에 한 번 연산하면 다음 네 문자열이 가능하다.

BCDABCD ABCABCD ABCDABC ABCDBCD

최종 암호화 문자열이 주어질 때, 어떤 원본 문자열에 한 번 이상의 연속 연산을 적용해 FJ가 이 문자열을 만들 수 있는 방법 수를 구하여라. 같은 암호화 결과를 내더라도 연산은 서로 다른 것으로 센다. 예를 들어 AA에서 AAA를 만드는 방법은 위 네 연산에 해당하는 네 가지이다.

입력

• $1$번째 줄: 길이가 최대 100인 문자열.

출력

• $1$번째 줄: 길이가 최소 2인 어떤 원본 문자열에 한 번 이상의 연속 연산을 적용해 이 문자열을 만드는 서로 다른 방법 수. 그런 방법이 없으면 0을 출력한다.

예제

입력 1

ABABA

출력 1

6

참고

FJ가 ABABA를 만드는 서로 다른 방법은 다음과 같다.

1. 다음 문자열로 시작: ABA -> AB+ABA
2. 다음 문자열로 시작: ABA -> ABA+BA
3. 다음 문자열로 시작: AB -> AB+A -> AB+ABA
4. 다음 문자열로 시작: AB -> AB+A -> ABA+BA
5. 다음 문자열로 시작: BA -> A+BA -> AB+ABA
6. 다음 문자열로 시작: BA -> A+BA -> ABA+BA

문제 작성자: Brian Dean과 Lewin Gan