반복 문자열 만들기

룰루에게 소문자 영어 알파벳으로 이루어진 문자열이 있다. 룰루는 이 문자열을 반복형으로 만들고 싶어 한다. 반복형 문자열은 글자 수가 짝수이고, 앞 절반이 뒤 절반과 정확히 같다. 예를 들어 "lulu", "abcabc", "xx"는 반복형이고, "xyx"와 "abac"는 반복형이 아니다.

반복형 문자열을 만들려면 룰루는 문자열에서 겹치지 않으면서 비어 있지 않은 부분 문자열 두 개를 고르고, 원래 문자열에 나타난 순서대로 이어 붙이면 된다.

룰루가 부분 문자열 두 개를 고르는 방법은 몇 가지인가? 두 방법은 사용한 부분 문자열 중 적어도 하나가 문자열의 다른 위치에서 왔다면 다른 것으로 본다.

문자열 "aaaa"를 생각해 보자.

• "aa"를 만드는 방법은 6가지이다. 각 "a"를 그 뒤에 나오는 "a"와 짝지으면 된다 ($1$+$2$, $1$+$3$, $1$+$4$, $2$+$3$, $2$+$4$, $3$+$4$).
• "aaaa"를 만드는 방법은 3가지이다: "a"+"aaa", "aa"+"aa", "aaa"+"a".

따라서 "aaaa"에서 이 방식으로 반복형 문자열을 만드는 방법은 9가지이다.

첫 줄에 문자열 $s$가 주어진다. $s$는 소문자 영어 알파벳으로 이루어지며, $1 ≤ |s| ≤ 800$이다.

룰루가 겹치지 않고 비어 있지 않은 부분 문자열 두 개를 원래 순서대로 이어 붙여 반복형 문자열을 만드는 방법의 수를 한 줄에 출력한다.