A palindrome is a string that reads the same forwards and backwards.
For example, "abba" and "racecar" are palindromes.
An odd palindrome is a palindrome with an odd length.
For example, "racecar" is an odd palindrome but "abba" is not.
The middle letter of an odd palindrome is called its center.
Limak has a String s consisting of N lowercase English letters.
For each valid i, let X[i] be the number of palidromic subsequences of s such that their center is s[i].
In other words:
For a fixed i, there are exactly 2^(N-1) ways to erase some characters of s other than the character s[i].
X[i] is the number of ways of erasing for which the string that remains to the left of s[i] is the reverse of the string that remains to the right of s[i].
For each i, compute the value Y[i] = ((i+1) * X[i]) modulo 1,000,000,007.
Then, compute and return the bitwise XOR of all the values Y[i]. |