회문의 역습

회문(palindrome)은 프로그래밍 대회에서 오랫동안 반복되어 온 소재이지만, 회문과 관련된 문제는 대체로 꽤 쉬운 편이었고, 그래서 회문들은 자신들이 홀대받는다고 느꼈다. 그리하여 회문 세계 총회에서는 회문들의 힘을 하나로 모아 경쟁 프로그래머들에게 본때를 보여 주기로 결정하였다.

회문은 교활해서 문자열 속에 자주 숨는다. 어떤 문자열에서 일부 문자를 지웠을 때 남은 문자들이 회문을 이루면, 그 회문이 문자열 속에 숨어 있었다고 말한다. 예를 들어 문자열 banaan 속에는 회문 aaa, naan, nan, b 등이 숨어 있다.

문자열의 각 문자에는 회문력(palindromic power)이 있다. 이 힘은 그 문자의 위치 번호($1$부터 센다)와, 그 문자에 숨어 있는 회문의 개수를 곱한 값이다. 여기서 지우는 방법이 서로 다르다는 것은 남긴 위치들의 집합이 다르다는 뜻이며, 남은 문자열이 같더라도 위치 집합이 다르면 서로 다른 경우로 센다. 즉 서로 다른 문자열이 아니라 위치들의 부분집합을 센다.

예를 들어 문자열 aaba의 네 문자의 회문력은 각각 $1 \cdot 5 = 5$, $2 \cdot 5 = 10$, $3 \cdot 3 = 9$, $4 \cdot 6 = 24$이다. 첫 번째 문자의 회문력이 $5$인 이유는 다음과 같다. 다른 문자들을 여러 조합으로 지우면 첫 번째 문자를 포함하는 경우가 $8$가지 나오고, 그중 $5$가지가 회문이다(별표로 표시). 점(.)은 지워진 문자를 뜻한다: a...*, a..a*, a.b., a.ba*, aa..*, aa.a*, aab., aaba.

회문들이 "힘을 하나로 모은다"는 것은 자신들의 비트를 모두 합쳐 아주 강해진다는 뜻이었다. 하지만 회문들은 두 가지를 미처 고려하지 못했다.

첫째, 그들의 힘은 마법 모듈러라는 프로그래밍 대회의 자연법칙에 의해 제한된다. 모두가 알듯이 마법 모듈러의 값은 $10^9 + 7$이다. 각 위치의 회문력을 구할 때에는 그 곱을 마법 모듈러로 나눈 나머지를 취해야 한다.

둘째, 힘의 비트들은 서로 상쇄되기 때문에, 이들을 합치면 힘의 합이 아니라 비트 단위 XOR($\oplus$) 연산의 결과가 된다. 문자열의 모든 문자의 회문력을 XOR한 결과를 그 문자열의 회문력이라고 부른다.

첫째 줄에 문자열의 길이 $N$ ($1 \le N \le 3000$)이 주어진다. 둘째 줄에 $N$개의 소문자 라틴 문자(a–z)로 이루어진 문자열이 주어진다.

주어진 문자열의 회문력을 한 줄에 출력한다.