카드섹션 timer 1s memory 16MB

진흥이네 반은 체육시간에 한사람이 영문자 한자씩 적힌 카드를 들고 카드섹션을 하기로 했다. 진흥이는 학생들중 일부가 카드를 들었을 때 팰린드롬(Palindrome)이 되는 경우가 몇 가지나 되는지 궁금해졌다.

팰린드롬(Palindrome)이란 앞으로 읽으나 뒤로 읽으나 같은 문자열을 말한다.
예를 들어, "A", "SOS", "MADAM" 과 같은 것들은 팰린드롬이지만, "ABCDE", "SSO" 는 팰린드롬이 아니다.
만약 학생들이 가지고 있는 카드가 순서대로 "ABA" 라고 한다면 팰린드롬이 가능한 경우는 A₁, B₂, A₃, A₁A₃, A₁B₂A₃의 다섯 가지이다. (문자 뒤의 첨자는 학생의 번호이다.)

학생들이 가지고 있는 카드가 "AAAA" 라면 A₁, A₂, A₃, A₄, A₁A₂, A₁A₃, A₁A₄, A₂A₃, A₂A₄, A₃A₄, A₁A₂A₃, A₁A₂A₄, A₁A₃A₄, A₂A₃A₄, A₁A₂A₃A₄의 15가지 팰린드롬이 가능하다.

즉, 문자열 구성이 같아도 선택된 학생이 다르다면 서로 다른 것으로 간주한다. 단, 학생의 순서는 바꿀수 없다. 따라서, "ABA"와 "AAB"는 카드의 종류와 개수는 같지만 팰린드롬이 가능한 경우의 수는 서로 다르다.

학생들이 가지고 있는 카드를 순서대로 문자열 형태로 입력받아 팰린드롬을 만들 수 있는 경우의 수를 구하는 프로그램을 작성하시오.