비밀 코드

농부 존에게는 소들에게 숨기고 싶은 비밀 메시지가 있다. 메시지는 길이가 2 이상이고 A부터 Z까지의 대문자로만 이루어진 문자열이다.

존은 메시지를 암호화하려고 연산을 여러 번 적용한다. 문자열 $S$에 연산을 한 번 적용하면 먼저 $S$의 첫 글자나 마지막 글자를 지워 길이를 하나 줄이고, 남은 문자열의 앞이나 뒤에 원래 문자열 $S$를 붙인다. 예를 들어 ABCD에 연산을 한 번 적용하면 다음 네 가지 결과가 나온다.

• BCDABCD
• ABCABCD
• ABCDABC
• ABCDBCD

암호화가 끝난 문자열이 주어진다. 길이가 2 이상인 어떤 문자열에서 시작해 연산을 한 번 이상 적용해 이 문자열을 만드는 방법이 몇 가지인지 세어라. 만들어진 문자열이 같아도 연산이 다르면 서로 다른 방법으로 센다. 예를 들어 AA에서 AAA를 만드는 방법은 위 네 연산에 하나씩 대응하는 네 가지다.

첫째 줄에 길이가 100 이하인 문자열이 주어진다. 문자열은 A부터 Z까지의 대문자로만 이루어져 있다.

길이가 2 이상인 어떤 문자열에 연산을 한 번 이상 차례로 적용해 주어진 문자열을 만드는 방법의 수를 출력한다. 그런 방법이 없으면 0을 출력한다.

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