The Palindromes Strike Back

Palindromes have been a recurring theme in programming contests through the ages, but the problems built around them have usually been rather easy — and that makes the palindromes feel unappreciated. So, at the World Congress of Palindromes, it was decided that the palindromes must unite their power and put competitive programmers in their place.

Palindromes are cunning and often hide themselves inside strings. A palindrome is hidden in a string when, after deleting some set of characters, the characters that remain form a palindrome. For example, the string banaan hides the palindromes aaa, naan, nan, b, and so on.

Every character of the string has a palindromic power. This power equals the character's position number (counting from $1$) multiplied by the number of palindromes hidden at that character. Two ways of deleting are considered different whenever the set of kept positions differs — even if the two resulting strings are identical. In other words, we count subsets of positions, not distinct strings.

For example, the palindromic powers of the four characters of aaba are $1 \cdot 5 = 5$, $2 \cdot 5 = 10$, $3 \cdot 3 = 9$, and $4 \cdot 6 = 24$. Why is the first character's power $5$? Deleting different combinations of the other characters yields $8$ subsets that keep the first character; of those, $5$ are palindromes (marked with an asterisk), where a dot denotes a deleted character: a...*, a..a*, a.b., a.ba*, aa..*, aa.a*, aab., aaba.

When the palindromes "unite their power", they pool all of their bits together to become overwhelmingly strong. But they overlooked two things.

First, their power is bounded by a law of nature of programming contests known as the Magic Modulus, whose value is $10^9 + 7$. When computing the palindromic power of a position, you must reduce that product modulo the Magic Modulus.

Second, the bits of the powers annihilate one another, so combining them yields not the sum of the powers but their bitwise XOR ($\oplus$). The XOR of the palindromic powers of all characters of the string is called the palindromic power of the string.

The first line contains the length of the string $N$ ($1 \le N \le 3000$). The second line contains a string of $N$ lowercase Latin letters (a–z).

Print, on a single line, the palindromic power of the given string.