지도

가장 말단의 선원도 우리가 보물을 찾으러 간다는 것을 안다. 나는 이 모든 것이 마음에 들지 않는다!

스몰렛 선장

1744년 긴 항해 중에 알렉산더 스몰렛 선장의 손에 보물의 위치가 표시된 고대 지도가 들어왔다. 하지만 그 내용을 해독하기는 쉽지 않았다.

스몰렛 선장의 선원들은 보물이 빨간 십자가에서 동쪽으로 $x$ 걸음 떨어진 곳에 있다고 짐작했지만, $x$의 값은 알아내지 못했다. 본토로 돌아온 알렉산더 스몰렛은 지식이 많은 현자에게 메시지 해독을 부탁했다. 현자의 말에 따르면 메시지에는 어떤 수가 숨어 있었다. 그 수를 구하려면 단어 사이의 공백을 모두 지운 뒤, 문자 세 개만 남기고 나머지를 지웠을 때 왼쪽에서 읽은 것과 오른쪽에서 읽은 것이 같은 세 글자 단어가 되는 방법의 수를 세야 한다.

스몰렛은 메시지에 숨은 수가 $x$라고 짐작했지만, 그 수를 계산하지는 못했다. 선장이 죽은 뒤 지도는 행방이 묘연해졌다가 이제 여러분의 손에 들어왔다. 비밀은 모두 풀렸으니 남은 일은 $x$를 계산하는 것이다.

입력은 지도에 적힌 메시지가 담긴 한 줄이다. 메시지의 길이는 $3 \cdot 10^5$을 넘지 않는다. 메시지에는 영어 소문자와 공백만 들어 있다. 메시지는 비어 있지 않으며, 공백으로 시작하거나 끝나지 않는다.

메시지에서 문자를 세 개만 남기고 나머지를 모두 지웠을 때, 남은 단어를 왼쪽에서 읽어도 오른쪽에서 읽어도 같게 만드는 방법의 수 $x$를 한 줄에 출력한다.

메시지 길이가 200 이하인 경우를 처리하는 풀이는 30점을 받는다. 길이가 5000 이하인 경우를 처리하는 풀이는 60점을 받는다.